Statistical: $|\Pr[E_K(m_0)\in T]-\Pr[E_K(m_1)\in T]|\leq\epsilon$

Computational: $|\Pr[A(E_K(m_0))=1]-\Pr[A(E_K(m_1))=1]|\leq\epsilon(n)$

What is the $1$ doing there? Why isn't it $Pr[A(E_K(m_0))\in T]$? Is there something deep behind these different notations? or is it simply a convention of the PPT $A$ having a boolean as a return value?

  • $\begingroup$ Where did you read? 1 means the adversary is successful. $\endgroup$
    – kelalaka
    Commented Apr 11, 2021 at 19:15
  • $\begingroup$ @kelalaka - where did i read what? $\endgroup$
    – ihadanny
    Commented Apr 11, 2021 at 19:17

1 Answer 1


You can define statistical security directly in terms of the statistical properties of different distributions. For example, you could define two distributions to be statistically close if their statistical distance is very small.

On the other hand, computational security is not precisely a statistical property of the given distributions. As such, the two distributions under consideration may not be similar at all, in fact, they may be super different! but what matters for this notion of security is that it is not efficient to distinguish between the two.

To formalize this idea, you need to talk about distinguishers, which are algorithms that receive an input from one of the two distributions and try to guess which distribution it comes from. This would the algorithm $A$ in your definition. The intuition of the definition is that such algorithm will output some fixed value ($1$, in this case) with almost the same probability, independently from which of the two distributions the input is sampled from.


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.