3
$\begingroup$

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

Is there a formal proof for it?

$\endgroup$
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\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$ – Ilmari Karonen Feb 3 '15 at 16:14
  • $\begingroup$ @Ilmari, looks like the link to CPA definition is broken. $\endgroup$ – doughgle Sep 6 '19 at 23:39
  • $\begingroup$ @doughgle: So it seems. Archive.org to the rescue. $\endgroup$ – Ilmari Karonen Sep 6 '19 at 23:59

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.