TransWikia.com

Is Computational Indistinguishability quantifiable?

Cryptography Asked by user9414424 on October 24, 2021

Is Computational Indistinguishability quantifiable?
I know that the success probability should be negligible, which however seems to be somewhat ambiguous.
Is it possible (and usual) to say that given encryption scheme is said to be something like it is computationally secure with some probability?
I’ve been using an IND-CPA secure public key crypto so far.

One Answer

The answer is yes. Formally, when a scheme is proven secure (relatively to a specific security game), a theorem states that no adversary $mathcal{A}$ couldn't win the security game except with a probability $f(lambda, m_1, m_2, dots)$.

With $f$ a function in $[0; 1]$, $lambda$ a parameter called the security parameter (in general when $lambda$ increases $f$ decreases as the efficiency (in time and space) of your protocol) and $m_1, dots m_n$ which determines (or just upper bound) the power capability of the adversary: For example $m_1$ could be the number of messages seen by the adversary. And $m_2$ could be the number of generic group operation (if we are in the generic group model).

You have first to determine $m_i$ (id est: If your adversary is your nephew, the NSA, your nephew in 2050, the NSA in 3850, etc). Then you choose lambda which verifies:

$f(lambda, m_1, m_2, dots) <frac{1}{2^{128}}$.

Particular case: Some result contain terms like $texttt{ADV}^P(lambda)$, with $P$ a well known computational problem (RSA, DH, LWE, etc). Then you have to check in the literature the best known attack to evaluate this term (or more simply which lambda is recommended).

Answered by Ievgeni on October 24, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP