Why can no stateless and deterministic encryption system be IND-CPA secure?

Is there a formal proof for it?


1 Answer 1


Here is the answer for why a deterministic public-key encryption scheme cannot be CPA secure.

For CPA security it is sufficient if an adversary can distinguish between encryptions of two messages $m_0$ and $m_1$. That is, an adversary gets to see an encryption $c \gets \textsf{Enc}(pk,m_b)$ for a random bit $b$ together with the public key $pk$. Now in order to figure out if $c$ is an encryption of $m_0$ all the adversary has to do is to recompute $\textsf{Enc}(pk,m_0)$ and check whether or not this value matches the given ciphertext thus breaking CPA security.

  • $\begingroup$ Essentially the same argument also works for symmetric ciphers, since the definition of IND-CPA security assumes that the attacker has access to an encryption oracle. $\endgroup$ Commented Feb 3, 2015 at 16:14
  • $\begingroup$ @Ilmari, looks like the link to CPA definition is broken. $\endgroup$
    – doughgle
    Commented Sep 6, 2019 at 23:39
  • $\begingroup$ @doughgle: So it seems. Archive.org to the rescue. $\endgroup$ Commented Sep 6, 2019 at 23:59

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.