Why can no stateless and deterministic encryption system be IND-CPA secure?
Is there a formal proof for it?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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$ – 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
