Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What is the difference between the two notions of computational and statistical indistinguishability?

share|improve this question
add comment

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
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 –  curious Dec 24 '13 at 22:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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