What is the difference between the two notions of computational and statistical indistinguishability?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Computationally indistinguishable typically means that your adversary is computationally bounded and that because of this they cannot distingush 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. They adversary, no matter how powerful, can not distinguish between the two.