The two asymptotically equivalent definitions of IND-CPA

There are two asymptotically equivalent definitions of IND-CPA for secret-key encryption schemes. I think the one-challenge one makes the proof neater.

Notice to Narrator users. It seems to me that Narrator in Windows 10 version 1809 will not read <span role=math aria-label=something>something</span> correctly. You might find it difficult to read this entry if you must use Narrator. (VoiceOver on macOS Mojave also refuses to read the math in Safari. VoiceOver on iOS is fine.) Vote for this feedback and this.

IND-CPA stands for INDistinguishability under Chosen Plaintext Attack, which is the second most basic security level we want from an encryption scheme (the easier one is semantic security, and the harder ones include IND-CCA1, IND-CCA2, IND-CCA3 and non-malleability related ones; cf. the CRYPTO 1998 paper by Bellare et al.).

For a public-key encryption scheme (Gen,Enc,Dec), the textbook definition of IND-CPA security is the following:

• The challenger runs $(\mathsf{p}\mathsf{k},\mathsf{s}\mathsf{k})\stackrel{\$}{\leftarrow }\mathsf{G}\mathsf{e}\mathsf{n}$ and sends $\mathsf{p}\mathsf{k}$ to the adversary.
• The adversary performs some computation, chooses $(m_0,m_1)$ and sends them to the challenger.
• The challenger runs $\mathsf{c}\mathsf{t}\stackrel{\$}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{p}\mathsf{k},m_b)$ for b←${0,1}, and sends $\mathsf{c}\mathsf{t}$ to the adversary.
• The adversary performs some computation and outputs a bit b′.

It’s well-known that IND-CPA security remains equivalent (the advantages are polynomially related) even if we allow multiple adaptive queries, because the adversary is capable of doing encryption by itself.

For a secret-key encryption scheme (G,E,D), the definition must allow multiple encryptions. A usual version taught (page 179) in class (in scribe note 9; however, UW Net ID is required to see the scribe notes) (also on Wikipedia, attributed to Bellare and Phillip) might be the following:

• The challenger runs $k\stackrel{\$}{\leftarrow }G$ and sample b←${0,1}.
• The adversary can adaptively present many challenges $(m_{i0},m_{i1})$ and get back E(k,mib​).
• The adversary outputs a bit b′.

Decoupling

Usually the proof of IND-CPA security of a secret-key scheme involves a hybrid argument that ‘switches’ the challenge encryptions one by one. However, the hybrid proof itself can be separated from the other parts. Also, the name ‘chosen plaintext attack’ suggests that the adversary gets to see many ciphertexts of plaintexts at its choice. Indeed, this is captured by the above definition of IND-CPA, in which the adversary can submit queries of the form $(m,m)$ to get a ciphertext of m. Of course, the adversary must still present a challenge in which the two plaintexts differ, otherwise there’s no chance that the adversary can distinguish the two cases.

The natural question thus arises: Can we decouple the indistinguishability with one challenge in the presence of ciphertexts of chosen plaintexts and the hybrid proof over the challenges, by giving the adversary the encryption oracle but allowing only one challenge query? Yes, and the lecture notes by Rafael Pass and abhi shelat define IND-CPA in this way (page 168; definition 168.1):

• The challenger runs $k\stackrel{\$}{\leftarrow }G$ and sample b←${0,1}.
• The adversary can adaptively present many chosen plaintexts $m_i$ and get back E(k,mi​).
• The adversary then presents an adaptive challenge $(m^{(0)},m^{(1)})$ and get back E(k,m(b)).
• The adversary can continue to adaptively present many chosen plaintexts $m_i$ and get back E(k,mi​).
• The adversary outputs a bit b′.

Obviously, this notion (call this IND-1-LR-many-Enc-CPA; LR means left/right) follows from the usual version (call that IND-many-LR-0-Enc-CPA). The usual version follows from IND-1-LR-many-Enc-CPA by a standard hybrid argument. IND-1-LR-many-Enc-CPA is minimal yet still reflects the attack model, chosen plaintext attack, thanks to the encryption oracle.

The benefit of IND-1-LR-many-Enc-CPA is that it eases the mind. In a not-so-simple encryption scheme, it is easier to write and read a proof where there is only one challenge, albeit in the presence of many ciphertexts of chosen plaintexts.

The usual version again

When we consider tight reductions (or concrete security), IND-many-LR-0-Enc-CPA might be the desired direct target of proof. This might be the case for public-key encryption schemes, too. For example, IND-many-LR-0-Enc-CPA of k-Lin-based encryption schemes can be tightly reduced to the underlying assumption using random self-reducibility, but the general hybrid proof incurs a security loss of q.