# Is there such a thing as perfect CPA security?

Consider the following experiment. If we require that $$\operatorname{P}\left( \mathcal A \text{ succeeds} \right) = \frac{1}{2}$$ for any adversary $\mathcal A$ in order to call the scheme $\Pi$ perfectly CPA secure, can such a scheme exist?

It would seem like this definition cannot be met since the adversary can use the oracle access to compute $\text{Enc}_k(m_i)$ for $i=1,2$ as many times as necessary until one of them coincides with $c\leftarrow \text{Enc}_k(m_b)$, at which point $\mathcal A$ knows what $b$ is. Is my thinking correct?

The CPA indistinguishability experiment definition that you give is taken from Katz & Lindell's textbook. In my copy (2nd Ed.), it's on page 74.

It would seem like this definition cannot be met since the adversary can use the oracle access to compute $\text{Enc}_k(m_i)$ for $i=1,2$ as many times as necessary until one of them coincides with $c\leftarrow \text{Enc}_k(m_b)$, at which point $\mathcal A$ knows what $b$ is. Is my thinking correct?

One thing you're missing is that earlier the chapter stipulates that only probabilistic polynomial time (PPT) adversaries will be considered. Earlier in the chapter (pp. 49-50):

However, when it comes to the computational power of the adversary, we will from now on model the adversary as efficient and thus only consider adversarial strategies that can be implemented in probabilistic polynomial time.

So the first problem with your adversary is that you've not demonstrated that it is a PPT algorithm. Significantly, if the number of calls to the encryption oracle is an exponential function of one of the security parameters (as brute force guessing algorithms tend to be), then it's disqualified.

The second problem is that the encryption algorithm is also PPT (see Definition 3.7, p. 52), which means it's probabilistic—it's allowed to make random choices. This means that you can't assume it's the oracle is mathematical function—calling $\text{Enc}_k(m)$ multiple times with the same $m$ can (and should!) produce different results.

Your adversary almost works, but not quite. If we denote by $N$ the cardinality of the set from which $\mathrm{Enc}$ (uniformly) chooses its random tape, then each call of the oracle will have a $1/N$ probability of choosing the same random tape as the one chosen during the actual encryption, or in other words a $\frac{N-1}{N}$ probability of not choosing it. After $k$ tries, there is a $\frac{(N-1)^k}{N^k} > 0$ probability that a match has not been found, hence your adversary does not always halt.

If it were possible for the adversary to arbitrarily choose $\mathrm{Enc}$'s random tape during an oracle call, then it could try them all, which would ensure that a match is always found, but that is not the case.

• I don't see a requirement the adversary will halt in any finite time. If Ek chooses tape at random the adversary will eventually halt though it may take a very long time. There is an infentisimally small chance of it taking longer than any constant time you choose which isn't the same as not stopping. Also the encryption oracle can be stateful and never ever repeat. – Meir Maor Sep 23 '17 at 12:48
• @Meir The requirement that any algorithm must always halt in finite time seems to me to be a pretty standard one. If OP wishes to forgo it, I think it should be explicitly mentioned in the question. Ditto if the encryption oracle is stateful. – fkraiem Sep 24 '17 at 1:10
• There are two reasons why I do not understand this answer: (1) There are no restrictions on the adversary, so why should it be impossible for the adversary to call all of the random tapes during an oracle call? (2) Even if it were impossible, this just means that the adversary does not have a 100% success rate but certainly the adversary will have a higher success rate than guessing. @fkraiem – CRYPTONEWBIE Sep 24 '17 at 6:23
• During an oracle call the adversary only supplies the message, and the random tape is chosen uniformly and independently of that of all the previous calls, because that's how the oracle works. – fkraiem Sep 24 '17 at 6:46
• And your second question is moot: the adversary does not always halt in finite time, so it is not a valid adversary. Maybe you could try modifying it a bit... – fkraiem Sep 24 '17 at 6:54