Why can no stateless and deterministic encryption system be IND-CPA secure?
Is there a formal proof for it?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communityHere 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.