What is the difference between the two notions of computational and statistical indistinguishability?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Computationally indistinguishable typically means that your adversary is computationally bounded and that because of this they cannot distinguish between, for example, two messages.
For example, say you encrypt (with proper padding) the messages $0$ and $1$ using RSA and send them to the adversary. We would not want the adversary to be able to distinguish which encrypts the $0$ and which encrypts the $1$. If the adversary is not computationally bounded, however, they can break RSA via factoring, recover the private key, and decrypt each ciphertext to get the plaintext. Then they would be able to distinguish.
Statistical indistinguishability is when the adversary is not computationally bounded. They should still not be able to tell the difference between, for example, two ciphertexts. An example of this would be the one-time-pad. Encrypt a message of all 1's with one pad and a message of all 0's with a different pad. The adversary, no matter how powerful, can not distinguish between the two.
-
3$\begingroup$ Also statistical indistinguishability is stronger than computational indistinguishability as there is not restriction on the computational power. So it might be the case that a scheme preserves computational indistinguishability but not the statistical indistinguishability $\endgroup$– curiousDec 24, 2013 at 22:10