Ciphertext indistinguishability

For a probabilistic asymmetric key encryption algorithm, indistinguishability under chosen plaintext attack (IND-CPA) is defined by the following game between an adversary and a challenger. For schemes based on computational security, the adversary is modeled by a probabilistic polynomial time Turing machine, meaning that it must complete the game and output a guess within a polynomial number of time steps. In this definition E(PK, M) represents the encryption of a message M under the key PK:

1. The challenger generates a key pair PK, SK based on some security parameter k (e.g., a key size in bits), and publishes PK to the adversary. The challenger retains SK.
2. The adversary may perform a polynomially bounded number of encryptions or other operations.
3. Eventually, the adversary submits two distinct chosen plaintexts ${\displaystyle \scriptstyle M_{0},M_{1}}$ to the challenger.
4. The challenger selects a bit b ${\displaystyle \scriptstyle \in }$ {0, 1} uniformly at random, and sends the challenge ciphertext C = E(PK, ${\displaystyle \scriptstyle M_{b}}$) back to the adversary.
5. The adversary is free to perform any number of additional computations or encryptions. Finally, it outputs a guess for the value of b.

A cryptosystem is indistinguishable under chosen plaintext attack if every probabilistic polynomial time adversary has only a negligible "advantage" over random guessing. An adversary is said to have a negligible "advantage" if it wins the above game with probability ${\displaystyle \scriptstyle \left({\frac {1}{2}}\right)\,+\,\epsilon (k)}$, where ${\displaystyle \scriptstyle \epsilon (k)}$ is a negligible function in the security parameter k, that is for every (nonzero) polynomial function ${\displaystyle \scriptstyle poly()}$ there exists ${\displaystyle \scriptstyle k_{0}}$ such that ${\displaystyle \scriptstyle |\epsilon (k)|\;<\;\left|{\frac {1}{poly(k)}}\right|}$ for all ${\displaystyle \scriptstyle k\;>\;k_{0}}$.

Although the adversary knows ${\displaystyle \scriptstyle M_{0}}$, ${\displaystyle \scriptstyle M_{1}}$ and PK, the probabilistic nature of E means that the encryption of ${\displaystyle \scriptstyle M_{b}}$ will be only one of many valid ciphertexts, and therefore encrypting ${\displaystyle \scriptstyle M_{0}}$, ${\displaystyle \scriptstyle M_{1}}$ and comparing the resulting ciphertexts with the challenge ciphertext does not afford any non-negligible advantage to the adversary.

While the above definition is specific to an asymmetric key cryptosystem, it can be adapted to the symmetric case by replacing the public key encryption function with an encryption oracle, which retains the secret encryption key and encrypts arbitrary plaintexts at the adversary's request.

The adversarial process of performing a chosen-plaintext attack is usually outlined in the form of a Cryptographic Game. To test for symmetric IND-CPA, the game described above is defined.[1] Let ${\displaystyle {\mathcal {K}}}$ be a key generation function, ${\displaystyle {\mathcal {E}}}$ be an encryption function, and ${\displaystyle {\mathcal {D}}}$ be a decryption function. Let ${\displaystyle {\mathcal {S}}{\mathcal {E}}=({\mathcal {K}},{\mathcal {E}},{\mathcal {D}})}$ be a symmetric encryption scheme. The game ${\displaystyle Guess}$ is defined as:

As many times as it would like, an adversary selects two plaintext messages of its own choosing and provides them to the LR oracle which returns a ciphertext encrypting one of the messages. An adversary's advantage is determined by its probability of guessing the value of b, a value chosen at random at the beginning of the game which determines the message that is encrypted in the LR oracle. Therefore, its advantage is defined as:[1]

Indistinguishability under non-adaptive and adaptive Chosen Ciphertext Attack (IND-CCA1, IND-CCA2) uses a definition similar to that of IND-CPA. However, in addition to the public key (or encryption oracle, in the symmetric case), the adversary is given access to a decryption oracle which decrypts arbitrary ciphertexts at the adversary's request, returning the plaintext. In the non-adaptive definition, the adversary is allowed to query this oracle only up until it receives the challenge ciphertext. In the adaptive definition, the adversary may continue to query the decryption oracle even after it has received a challenge ciphertext, with the caveat that it may not pass the challenge ciphertext for decryption (otherwise, the definition would be trivial).

1. The challenger generates a key pair PK, SK based on some security parameter k (e.g., a key size in bits), and publishes PK to the adversary. The challenger retains SK.
2. The adversary may perform any number of encryptions, calls to the decryption oracle based on arbitrary ciphertexts, or other operations.
3. Eventually, the adversary submits two distinct chosen plaintexts ${\displaystyle \scriptstyle M_{0},\,M_{1}}$ to the challenger.
4. The challenger selects a bit b ∈ {0, 1} uniformly at random, and sends the "challenge" ciphertext C = E(PK, ${\displaystyle \scriptstyle M_{b}}$) back to the adversary.
5. The adversary is free to perform any number of additional computations or encryptions.
   1. In the non-adaptive case (IND-CCA1), the adversary may not make further calls to the decryption oracle.
   2. In the adaptive case (IND-CCA2), the adversary may make further calls to the decryption oracle, but may not submit the challenge ciphertext C.
6. Finally, the adversary outputs a guess for the value of b.

A scheme is IND-CCA1/IND-CCA2 secure if no adversary has a non-negligible advantage in winning the above game.

Sometimes we need encryption schemes in which the ciphertext string is indistinguishable from a random string by the adversary.[2]

If an adversary is unable to tell if a message even exists, it gives the person who wrote the message plausible deniability.

Some people building encrypted communication links prefer to make the contents of each encrypted datagram indistinguishable from random data, in order to make traffic analysis more difficult.[3]

Some people building systems to store encrypted data prefer to make the data indistinguishable from random data in order to make data hiding easier. For example, some kinds of disk encryption such as TrueCrypt attempt to hide data in the innocent random data left over from some kinds of data erasure. As another example, some kinds of steganography attempt to hide data by making it match the statistical characteristics of the innocent "random" image noise in digital photos.

To support such deniable encryption systems, a few cryptographic algorithms are specifically designed to make ciphertext messages indistinguishable from random bit strings.[4][5][6]

Most applications don't require an encryption algorithm to produce encrypted messages that are indistinguishable from random bits. However, some authors consider such encryption algorithms to be conceptually simpler and easier to work with, and more versatile in practice—and most IND-CPA encryption algorithms apparently do, in fact, produce encrypted messages that are indistinguishable from random bits.[7]