Ciphertext Indistinguishability

Ciphertext indistinguishability ( German indistinguishability of ciphertexts ) is a term that is used in security proofs of encryption methods. In a method with this property can not distinguish between the ciphertexts of two plaintexts an attacker, even if he knows the plaintexts.

Motivation

To speak about the security of encryption, one must first be clear about what exactly is meant by security. The first thought that the attacker from the cipher text can not derive the plaintext may be, falls short. This fact is not excluded that an attacker gains information about parts of the plaintext, as long as it can not deduce the whole plaintext. It must therefore be at least require that the attacker can not learn any information about the plaintext. Also this formulation is not sufficient in some circumstances. If a public-key encryption method is in fact deterministic ( ie with the same input always produces the same output supplies, as is the case for example in the textbook RSA encryption ) and the attacker can restrict the plaintext space ( he knows, for example, that the encrypted message is either "yes" or "no" ), it can encrypt all possible plaintexts with the public key. Then he can by simply comparing the secret text with the secret texts that he has produced, determine the corresponding plaintext. It is therefore necessary to define a security term, in which this is not possible.

Motivation of IND - CPA

It is not generally useful, "Security" to speak with cryptographic methods by without having to qualify this in more detail. A security concept states that an attacker a certain goal can not reach. The definition thus consists of two parts: an attacker with capabilities just described, and the security target. Ciphertext indistinguishability (IND ) is a security goal, namely that it should not be possible for an attacker to distinguish between the encryption of any two plaintexts of the same length ( the encryptions of two plaintexts of different lengths may differ by the length of the cipher, therefore, the confidentiality of length of the plaintext is generally not required ). So this is true even in unfavorable choice of plain texts, the attacker gets to choose two plaintexts, one of which is encrypted. Attacker to different strengths can be defined. In general, the attacker is limited in its duration to prevent it searches the whole key space or tasks set, which are practically insoluble in the real world where computing power is also not available in unlimited quantities. In an asymmetric encryption method also must always be assumed that the attacker knows the public key. He can even encrypt arbitrary plaintexts of his choice and compare it with the ciphertext to learn something about the unknown plaintext. This attack is called chosen- plaintext attack (CPA ). Thus, an encryption method has the security level IND - CPA ( indistinguishability under chosen ciphertext plaintext attacks) if it can not succeed CPA attacker to achieve the goal IND, so to distinguish the ciphertexts of two self-chosen plaintexts.

Definition of IND - CPA

To express this formally, the experiment IND - CPA is defined, which runs between two probabilistic algorithms with polynomial ( in a security parameter ) time limitation, the attacker A and the neighborhood U in five steps.

If the environment is a "1 " outputs, the attacker has guessed correctly. An attacker who in the fourth step, regardless of everything that has happened before, a random bit and pulls it outputs is correct with probability 1/2. An encryption method is called secure if no attacker has a probability of success, which is significantly higher than 1/2, ie when is negligibly small ( if it is smaller than for any polynomial ) IND - CPA. A negligible difference must be permitted because it is very easy for an attacker to increase its success probability more than 1 /2: He simply advises a secret key and thus tries to decrypt the ciphertext. The probability of success here is very small, but greater than 0, it is important in the definition of that over the attacker until his term restriction no assumptions are made.

The term IND - CPA appeared in 1984 in Goldwasser and Micali under the name of " polynomial security " ( polynomial security). The above definition is formally not entirely correct, because an algorithm in computer science after the issue stops. An attacker thus consists of two algorithms, one of which spends the first two plaintexts and its condition. The second takes as input the two plaintexts, the state and the ciphertext and is a bit off. By transferring the state of the second algorithm can also be understood as a continuation of the first.

IND -CCA

The above-introduced CPA attacker is not the strongest. The stronger security notion IND -CCA obtained if the attacker in addition to the public key decryption oracle will be granted. An oracle is an algorithm that provides only inputs outputs, but can not be analyzed. Thus, the secret key contained in the decryption oracle, the attacker can not be accessed. The attacker can then be decrypted any ciphertexts in Step 2 and 4, with the exception of the secret text that he got in step 3. This attacker model is called adaptive chosen- ciphertext attack (CCA ). Its practical relevance was demonstrated in 1998, when it Daniel Bleichenbacher managed to lead them against the defined in PKCS # 1 IND - CPA - secure RSA variant a realistic attack in this model.

In the literature sometimes distinguishes between CCA1 and CCA2 - attackers. The CCA2 attacker is described above as CCA, while the CCA1 attacker has the decryption oracle only in step 2 are available. Because by the queries to the decryption oracle can not depend on the ciphertext in Step 3, this attack is also called ciphertext nichtadaptiver chosen- attack.