IND-CPA security

From CRYPTUTOR

IND-CPA security is a security definition for private- or public-key encryption schemes. At a high level, IND-CPA security means that no adversary can distinguish between encryptions of different messages, even when allowed to make encryptions on its own.

The "IND" part of the name IND-CPA comes from the fact that it is an indistinguishability-based security definition (the adversary tries to distinguish between encryptions of two different messages). The "CPA" part stands for chosen plaintext attack, because in the IND-CPA model, adversaries are allowed to compute encryptions of plaintexts that they can choose.

Definition

Let A be an adversary, which we model as an arbitrary non-uniform PPT machine (polynomial in the implicit security parameter of the encryption scheme). We define the following experiment/game played against A:

IND-CPA Distinguishability Experiment (for private-key encryption):

1. We (privately) choose a key K according to the key generation algorithm: .
2. We (privately) choose a random bit .
3. Repeatedly do:
   • A is allowed (any number of times) to query an oracle that computes the functionality .
   • Challenge: A outputs two messages, and .
   • Response: We give A the ciphertext
4. A outputs (i.e, a guess for our b).

We say that the advantage of A in this experiment is .

When we say that A can query an oracle for , we mean that A may give any message m and receive in response. Note that these responses are encryped under the same key K as the "challenge response."

An encryption scheme is -IND-CPA secure if:

For all adversaries A, the advantage of A in the IND-CPA experiment is at most

When is negligible in the encryption scheme's security parameter, we omit it and simply call the scheme IND-CPA secure.

Differences between IND-CPA and IND-onetime

In IND-onetime security, the adversary is given only one encryption, and in isolation. By including an encryption oracle, IND-CPA security models the fact that the adversary may know many other ciphertexts, and may have complete choice over which plaintexts he sees encryptions of. So unlike in one-time encryption, CPA security must hold in the presence of other ciphertexts.

An important consequence is that an IND-CPA secure encryption scheme must be randomized. That is, is a randomized algorithm, and can be viewed as a random variable. This is necessary because if were deterministic, the adversary could just ask the encryption oracle for the unique encryptions of and and see which one matches .

Modifications

Using an application of a hybrid argument, it can be shown that only one "challenge-response" phase is necessary. It does not affect the definition of security to remove the repeating loop (line 3).

However, if the loop remains, we can remove the adversary's access to an encryption oracle without loss of generality. Instead of querying the oracle for an encryption of m, the adversary can simply give (m,m) as a challenge, and it will receive an encryption of m as a response.

Public-key encryption

Only a slight modification of the IND-CPA experiment is needed to accomodate public-key encryption:

IND-CPA Distinguishability Experiment (for public-key encryption):

1. We choose a key pair according to the key generation algorithm. We give PK to the adversary and keep SK private.
2. We (privately) choose a random bit .
3. Challenge: A outputs two messages, and .
4. Response: We give A the ciphertext .
5. A outputs (i.e, a guess for our b).

As in the private-key experiment, the "challenge-response" phase need not be repeated. Unlike in the private-key experiment, the adversary does not need an oracle for the encryption functionality -- the adversary knows the public key and the encryption algorithm, and thus can generate encryptions itself.

See also

• SIM-CPA security
• Equivalence of IND-CPA and SIM-CPA