How can I understand the gap between CPA and CCA1?

I have read lots of books about CPA,CCA1,CCA2. I understand how to get an example satisfies CPA but not CCA2. However, I can't find such a scheme which is CPA but not CCA1. What is the extra advantage by lunch attack?

• Perhaps this helps.
– fgrieu
Mar 8 at 10:12

As a general rule most counterexamples will be very contrived. If you don't mind that, it's actually not too hard to come up with a separating example.

First consider what power we have in CCA1 that we don't have in CPA. We get to make decryption queries, but only before receiving the challenge ciphertext. This means, most common CCA attacks will simply not work, because they rely on making decryption queries that depend on the challenge ciphertext.

So how can access to the decryption oracle help us? Well, decryption evaluates a function of the secret key! So it is entirely conceivable that a cleverly crafted query might leak something about the secret key. And in particular, no matter how bonkers we design our decryption algorithm, it will not impact CPA security, because CPA security is completely independent of the decryption algorithm.

So, how to get a counterexample that leaks the key? When crafting counterexamples it is often helpful to ask yourself:

What is the absolutely most ridiculously stupid thing the scheme could do?

In this case the answer is that the decryption algorithm might simply output the secret key when we query it. Now, if we want to maintain correctness, i.e. that $$\Pr[\mathsf{Dec}(\mathsf{sk},\mathsf{Enc}(\mathsf{pk},m))=m]=1$$ for all messages $$m$$ we need to be a bit careful. We can't simply define $$\mathsf{Dec}(\mathsf{sk},c)=\mathsf{sk}$$. But correctness only makes a statement on the behavior of the decryption algorithm when it is evaluated on ciphertexts in the image of the encryption algorithm and there's absolutely nothing that says what it must do if we feed it something malformed.

So let's finally do this. Let $$(\mathsf{Gen}',\mathsf{Enc}',\mathsf{Dec}')$$ be a CPA secure public key encryption scheme. We define a new encryption schme defined as follows:

$$\mathsf{Gen}(1^\lambda) := \mathsf{Gen}'(1^\lambda)\qquad \mathsf{Enc}(\mathsf{pk},m):=\mathsf{Enc}'(\mathsf{pk},m)\Vert 0$$ $$\mathsf{Dec}(\mathsf{sk},c\Vert b) := \begin{cases}\mathsf{Dec}(\mathsf{sk},c)& \text{if } b=0\\\mathsf{sk}&\text{if }b=1\end{cases}$$

So what does this do? It behaves exactly like the CPA secure scheme, except that it append a $$0$$ bit to the ciphertext when encrypting. I'll leave proving that this preserves CPA security as an exercise.

When decrypting, the scheme checks if the last bit is $$0$$ and if it is, behaves normally. If the bit is $$1$$ however, it behaves in most catastrophically stupid way possible and outputs the secret key.

It should be obvious that this scheme can't possibly be CCA1 secure. You can just query any ciphertext ending in $$1$$ and get the secret key that you can use for decryption of the challenge ciphertext later.

Is this a realistic example of an encryption scheme? No, obviously not, it's terribly contrived. But it does show us that letting the adversary evaluate a function of the secret key can end very badly.

• Thank you very much. Your answer helps me a lot. Mar 8 at 13:30