In cryptography, a reasonable computational complexity definition for an encryption scheme, is 3 algorithms, (Generate, Encrypt, Decrypt) where encrypt and decrypt can be probabilistic polynomial algorithms.

My question is why are the encryption and decryption not deterministic?


If you use a deterministic encryption algorithm, then for the same message and same key, you will get the same cipher text.

For many messages, an adversary will be able to distinguish between different messages.

I could not think of a situation where the decryption was also probabilistic, so I’m guessing this may have been a typo. Please correct me if I’m wrong.

My think was that if the decryption was not deterministic, the when bob receives the same message, twice it will decrypt to two different plain-texts.

  • 2
    $\begingroup$ To complete this answer: obviously the key gen algorithm needs to be probabilistic, otherwise the same input (security parameter) would always result in the same keys. That would be pretty useless as encryption scheme. $\endgroup$ – tylo Jun 30 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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