Equivalence of IND-CPA and SIM-CPA

From CRYPTUTOR

Here we show that the two security definitions based on chosen plaintext attacks, IND-CPA security and SIM-CPA security, are equivalent definitions.

There are several possible modifications to the IND-CPA definition which do not change the security. For simplicity in this proof, we use the variant where the adversary can give multiple challenges, but does not have access to an encryption oracle.

SIM-CPA implies IND-CPA

Intuitively, the IND-CPA experiment can be viewed as a special case of the interactions covered in the broad SIM-CPA definition.

If SIM-CPA holds for an encryption scheme, then it holds with respect to an environment which "plays the IND-CPA experiment" against an adversary (flipping a random bit b, receiving challenge pairs from the adversary, and asking Alice to send ), outputting 1 if the adversary succeeds in the experiment. In the real world of SIM-CPA, this environment outputs 1 with probability 1/2 plus the IND-CPA advantage of the adversary. In the ideal world, the simulator's input is independent of the bit b, so the environment outputs 1 with probability exactly 1/2. By the SIM-CPA guarantee, these two probabilities must be negligibly close, so the IND-CPA advantage of the adversary is negligible.

This holds for any adversary, so the encryption scheme is IND-CPA secure.

IND-CPA implies SIM-CPA

Assuming IND-CPA holds for an encryption scheme, we will show that SIM-CPA also holds. To do this, we must demonstrate a simulator S_A for each real-world SIM-CPA adversary A. Our simulator is the following:

Simulator S_A for the SIM-CPA experiment:

• Choose a key .
• Interact with the environment just as A does.
• When Alice sends a message to Bob, and A expects to eavesdrop the ciphertext, give it , where m ^* is some fixed message in the message space (say, the all-zeroes string).

We must now show that for an arbitary A and environment E, the difference between the real-world and ideal-world (using this S_A) experiment outcomes is negligible. Call that difference ε.

To show that it is negliglble, we construct an adversary A ^* for the IND-CPA experiment which does the following:

A ^* : Adversary for IND-CPA:

1. Simulate the interactions of A and E as in the real-world SIM-CPA experiment.
2. Whenever E would give a message m to Alice to encrypt, give a challenge (m₀,m₁) = (m ^* ,m), where m ^* is the fixed message from the definition of S_A. Then give the resulting response to A.
3. When E outputs a bit, use that as b', our guess for b.

Now suppose we run the IND-CPA experiment against A ^* . When b = 1, A and E are running exactly as in the real world SIM-CPA experiment (A gets encryptions of the messages that E gives to Alice). When b = 0, they are running exactly as in the ideal world SIM-CPA experiment (A gets an encryption of m ^* every time, as in the simulation of S_A).

Now the probability that A ^* succeeds in its IND-CPA experiment is:

So the IND-CPA advantage of A ^* is . Since we assumed that the encryption scheme is IND-CPA secure, this quantity must be negligible. This implies that ε is negligible, as desired.