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.
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.
Security in terms of indistinguishability has many definitions, depending on assumptions made about the capabilities of the attacker.
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
The adversarial process of performing a chosen-plaintext attack is usually outlined in the form of a Cryptographic Game.
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).
A scheme is IND-CCA1/IND-CCA2 secure if no adversary has a non-negligible advantage in winning the above game.
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.
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.
[7] Indistinguishability is an important property for maintaining the confidentiality of encrypted communications.
Sometimes these implications go in both directions, making two definitions equivalent; for example, it is known that the property of indistinguishability under adaptive chosen ciphertext attack (IND-CCA2) is equivalent to the property of non-malleability under the same attack scenario (NM-CCA2).
This equivalence is not immediately obvious, as non-malleability is a property dealing with message integrity, rather than confidentiality.