# Proving that there is no scheme which would be perfectly CPA-secure

A private-key encryption scheme Π = (Gen, Enc, Dec) has perfectly indistinguishable encryptions under a chosen-plaintext attack, if for all probabilistic polynomial-time adversaries A it holds that Pr[PrivK_cpa(n) = 1] = 1/2. I need to show that there is no encryption scheme that can satisfy this definition.

The perfect indistinguishably under a chosen-plaintext attack: Pr[PrivK_cpa = 1] = 1/2

implicates

the perfect indistinguishably in the presence of eavesdropper: Pr[PrivK_eav = 1] = 1/2.

Which, in turn, implicates perfect secrecy: Pr[Enc_K (m) = c] = Pr[Enc_K (m') = c] for all m, m' from M, c from C.

Is my argumentation correct to this point? If so, could you, please, tell how can I now find the contradiction between the scheme being perfectly secret and perfectly indistinguishable under a chosen-plaintext attack? Should I find the contradiction using the definition of the perfect secrecy (above-mentioned) or should I use the fact that |K| should be >= |M|?

I saw this post Is there such a thing as perfect CPA security? with the same question but it does not help as there the fact that Enc is probabilistic rather than deterministic is mostly discussed.

• Perfect indistinguishability does not make any sense, since you would have to argue that exactly $0.5$ answer correctly. And for that you need to actually iterate somehow over all adversaries, if you restrict those to PPTs. Additionally, a CPA adversary trivially breaks deterministic encryption by querying both messages - so it makes sense to only consider probabilistic encryption. – tylo Jul 10 '18 at 15:39

This notion does not really make sense since the way that perfect secrecy is reached is by there not being enough information in a given ciphertext to tell anything about the message, so without the key an attacker knowns nothing.

This is information theoretic security and is unbounded.

If we intruduce a encryption oracle, given enough time and adversary will find the message by trying them all untill one works.

We can add extra constraints like making the adversary ppt but then we are not longer talking information theoretic security.

• No need to introduce an oracle. An adversary can just try and encrypt all possible messages with all possible random input (if the cipher is non-deterministic). As long as the cipher is not perfectly secret it should be possible to determine that the correct plaintext was entered: just check if the ciphertext matches. Completely computationally infeasible of course, but yeah, theoretic security... – Maarten Bodewes Aug 9 '18 at 13:00

I suspect the answer to this question will somewhat depend on your definition of an encryption scheme. In particular, can the key have an infinite number of bits, and can the encryption function Enc be stateful (so that it can make sure to never use the same key bits twice)?

If the answer to both questions is yes, then I believe it should be possible to define a one-time-pad-like scheme that is perfectly CPA-secure. The basic idea is that the key should consist of (or can be bijectively mapped into) an infinite number of infinitely long bit streams, and the encryption algorithm stores a message counter. To encrypt a message, it first increments the counter, extracts the bit stream indicated by the counter from the key, takes the prefix of this bit stream equal to the message in length, and XORs it with the message. Finally, it prepends the current value of the counter to the message (in some manner that allows it to be unambiguously extracted by the decryption algorithm) and returns the result. If I'm not mistaken, a scheme like this should provide perfect secrecy for an unlimited number of messages, and thus be perfectly CPA-secure even against arbitrarily powerful adversaries.

On the other hand, if the encryption algorithm is not stateful (and so cannot remember which key streams it has already used), then there's a non-zero change that it will use the same key material to encrypt two messages. And if the key material itself is finite, then this must eventually happen after sufficiently many encryptions, whether the encryption algorithm is stateful or not. Either way, an attacker with unlimited oracle access can exploit this by repeatedly querying the oracle for encryptions of their challenge messages until the result matches the challenge ciphertext.

In fact, for non-stateful encryption algorithms, the attacker doesn't even need unlimited oracle access to have a non-zero advantage, since there's always a non-zero probability that even a single query will just happen to yield a match. We can make this probability negligible, but not zero. On the other hand, a stateful encryption algorithm could be designed to avoid reusing a keystream for any given number of encryptions, but only if the key was long enough to permit this. In particular, asymptotically, a super-polynomial number of queries before a keystream is reused would seem to require a super-polynomial key length (and thus, presumably, a super-polynomial running time for the key generator).

The perfect indistinguishably under a chosen-plaintext attack: Pr[PrivK_cpa = 1] = 1/2

Is my argumentation correct to this point?

Assuming that the adversary has access to the public key, then here is an adversary that achieves an advantage $$> 1/2$$:

• Select a set of random coins; send them through the $$Gen$$ function

• Compare the public key generated with the public key presented

• If they are the same, use the private key generated to decrypt the ciphertext and use the resulting plaintext to make the decision.

• If they are not the same, select a random bit and use that as the output.

Now, if this procedure selects a set of random coins that just happen to be the same as the coins used during the original key generation process, then this always achieves the correct answer (or, at least, with high probability if the public key system has a small probability of decryption failure); if it does not, then this gives the correct answer with probability at least 1/2 ("at least" because there may be other sets of random coins that result in the same public key; those would also give the correct answer).

Hence, if $$\lambda$$ random coins were used in the key generation process, this gives the correct answer with probability $$2^{-\lambda} + 0.5(1 - 2^{-\lambda}) > 1/2$$