In the classic crypto textbook "Introduction to Modern Cryptography" by Jonathan Katz and Yehuda Lindell, there is a definition for indistinguishable encryption in the presence of an eavesdropper as such that for every probabilistic polynomial time adversary A there is a negligible function negl(n) such that

$\Pr[PrivK_{A,\Pi}=1] \leq negl(n)$

where PrivK is the indistinguishability experiment and for the purpose of this question we only need to know that the experiment outcome is 1 iff the adversary makes the correct guess.

My doubts are as follows. Consider a sequence of probabilistic polynomial time adversaries $\{A_i\}_{i>=1}$ whose advantage in the indistinguishability experiment is bounded by the following sequence of negligible functions

$\Pr[PrivK_{A,\Pi}=1] \leq negl_i(n) = \frac{1}{(1+1/i)^n}$

Clearly it is necessary for the above conditions to hold for a indistinguishable encryption. But is it a correct model/condition for real-world applications? For example, in practice we typically choose a sufficiently large n and set up some encryption scheme. However, there is the always some adversary $A_i$ that wins the experiment with probability close to one. So what's wrong?


1 Answer 1


Depends on how different your algorithms are. If you can compute $A_i$ from $i$ in polynomial time, then $A'$ with $A'(n) = A_n(n)$ is a polynomial time adversary too and violates the assumption (as it has non-negligible success probability). This would make your series of $A_i$ uniform and is one usual class of adversaries to consider.

If you'd like your crypto system to be secure against any such series of polynomial bounded adversaries you have to consider non-uniform adversaries (at least non-uniform in polynomial time), by e.g. defining a single adversary as a series of (randomized) circuits with polynomial size.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.