Ciphertext indistinguishability

Ciphertext indistinguishability is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message they encrypt. The property of indistinguishability under chosen plaintext attack is considered a basic requirement for most provably secure public key cryptosystems, though some schemes also provide indistinguishability under chosen ciphertext attack and adaptive chosen ciphertext attack. Indistinguishability under chosen plaintext attack is equivalent to the property of semantic security, and many cryptographic proofs use these definitions interchangeably. Ciphertext indistinguishability is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message they encrypt. The property of indistinguishability under chosen plaintext attack is considered a basic requirement for most provably secure public key cryptosystems, though some schemes also provide indistinguishability under chosen ciphertext attack and adaptive chosen ciphertext attack. Indistinguishability under chosen plaintext attack is equivalent to the property of semantic security, and many cryptographic proofs use these definitions interchangeably. A cryptosystem is considered secure in terms of indistinguishability if no adversary, given an encryption of a message randomly chosen from a two-element message space determined by the adversary, can identify the message choice with probability significantly better than that of random guessing (​1⁄2). If any adversary can succeed in distinguishing the chosen ciphertext with a probability significantly greater than ​1⁄2, then this adversary is considered to have an 'advantage' in distinguishing the ciphertext, and the scheme is not considered secure in terms of indistinguishability. This definition encompasses the notion that in a secure scheme, the adversary should learn no information from seeing a ciphertext. Therefore, the adversary should be able to do no better than if it guessed randomly. Security in terms of indistinguishability has many definitions, depending on assumptions made about the capabilities of the attacker. It is normally presented as a game, where the cryptosystem is considered secure if no adversary can win the game with significantly greater probability than an adversary who must guess randomly. The most common definitions used in cryptography are indistinguishability under chosen plaintext attack (abbreviated IND-CPA), indistinguishability under (non-adaptive) chosen ciphertext attack (IND-CCA1), and indistinguishability under adaptive chosen ciphertext attack (IND-CCA2). Security under either of the latter definition implies security under the previous ones: a scheme which is IND-CCA1 secure is also IND-CPA secure, and a scheme which is IND-CCA2 secure is both IND-CCA1 and IND-CPA secure. Thus, IND-CCA2 is the strongest of the three definitions of security. 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: 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 ( 1 2 ) + ϵ ( k ) {displaystyle scriptstyle left({frac {1}{2}} ight),+,epsilon (k)} , where ϵ ( k ) {displaystyle scriptstyle epsilon (k)} is a negligible function in the security parameter k, that is for every (nonzero) polynomial function p o l y ( ) {displaystyle scriptstyle poly()} there exists k 0 {displaystyle scriptstyle k_{0}} such that | ϵ ( k ) | < | 1 p o l y ( k ) | {displaystyle scriptstyle |epsilon (k)|;<;left|{frac {1}{poly(k)}} ight|} for all k > k 0 {displaystyle scriptstyle k;>;k_{0}} . Although the adversary knows M 0 {displaystyle scriptstyle M_{0}} , M 1 {displaystyle scriptstyle M_{1}} and PK, the probabilistic nature of E means that the encryption of M b {displaystyle scriptstyle M_{b}} will be only one of many valid ciphertexts, and therefore encrypting M 0 {displaystyle scriptstyle M_{0}} , M 1 {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. Let K {displaystyle {mathcal {K}}} be a key generation function, E {displaystyle {mathcal {E}}} be an encryption function, and D {displaystyle {mathcal {D}}} be a decryption function. Let S E = ( K , E , D ) {displaystyle {mathcal {S}}{mathcal {E}}=({mathcal {K}},{mathcal {E}},{mathcal {D}})} be a symmetric encryption scheme. The game G u e s s {displaystyle Guess} is defined as: