Ciphertext indistinguishability is a property of many
encryption
In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can de ...
schemes. Intuitively, if a
cryptosystem possesses the property of
indistinguishability, then an adversary will be unable to distinguish pairs of
ciphertext
In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext ...
s based on the message they encrypt. The property of indistinguishability under
chosen plaintext attack
A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts.Ross Anderson, ''Security Engineering: A Guide to Building Dependable Distributed Systems'' ...
is considered a basic requirement for most
provably secure
Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields.
Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...
public key cryptosystem
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
s, though some schemes also provide indistinguishability under
chosen ciphertext attack
A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the hidd ...
and
adaptive chosen ciphertext attack
An adaptive chosen-ciphertext attack (abbreviated as CCA2) is an interactive form of chosen-ciphertext attack in which an attacker first sends a number of ciphertexts to be decrypted chosen adaptively, and then uses the results to distinguish a tar ...
. 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 (). If any adversary can succeed in distinguishing the chosen ciphertext with a probability significantly greater than , 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.
Formal definitions
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
Secure may refer to:
* Security, being protected against danger or loss(es)
**Physical security, security measures that are designed to deny unauthorized access to facilities, equipment, and resources
**Information security, defending information ...
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
A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts.Ross Anderson, ''Security Engineering: A Guide to Building Dependable Distributed Systems'' ...
(abbreviated IND-CPA), indistinguishability under (non-adaptive)
chosen ciphertext attack
A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the hidd ...
(IND-CCA1), and indistinguishability under
adaptive chosen ciphertext attack
An adaptive chosen-ciphertext attack (abbreviated as CCA2) is an interactive form of chosen-ciphertext attack in which an attacker first sends a number of ciphertexts to be decrypted chosen adaptively, and then uses the results to distinguish a tar ...
(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.
Indistinguishability under chosen-plaintext attack (IND-CPA)
For a probabilistic
asymmetric key encryption algorithm
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic al ...
, indistinguishability under
chosen plaintext attack
A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts.Ross Anderson, ''Security Engineering: A Guide to Building Dependable Distributed Systems'' ...
(IND-CPA) is defined by the following game between an adversary and a challenger. For schemes based on
computational security
In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where ''efficiently'' typically means "in polynomial time"). It is not known how to prove (uncondition ...
, the adversary is modeled by a
probabilistic polynomial time Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
, 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'':
#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''.
#The adversary may perform a polynomially bounded number of encryptions or other operations.
#Eventually, the adversary submits two distinct chosen plaintexts
to the challenger.
#The challenger selects a bit ''b''
uniformly at random, and sends the ''challenge'' ciphertext ''C'' = E(PK,
) back to the adversary.
#The adversary is free to perform any number of additional computations or encryptions.
#Finally, the adversary 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
, where
is a
negligible function In mathematics, a negligible function is a function \mu:\mathbb\to\mathbb such that for every positive integer ''c'' there exists an integer ''N'c'' such that for all ''x'' > ''N'c'',
:, \mu(x), 0 such that for all ''x''  ...
in the security parameter ''k'', that is for every (nonzero) polynomial function
there exists
such that
for all
.
Although the adversary knows
,
and PK, the probabilistic nature of E means that the encryption of
will be only one of many valid ciphertexts, and therefore encrypting
,
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
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
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.
Symmetric IND-CPA Game, Formalized
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
be a key generation function,
be an encryption function, and
be a decryption function. Let
be a symmetric encryption scheme. The game
is defined as:
![IND-CPA_Guess_Cryptographic_Game](https://upload.wikimedia.org/wikipedia/commons/8/84/IND-CPA_Guess_Cryptographic_Game.svg)
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:
Indistinguishability under chosen ciphertext attack/adaptive chosen ciphertext attack (IND-CCA1, IND-CCA2)
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).
#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''.
#The adversary may perform any number of calls to the encryptions and decryption oracle based on arbitrary ciphertexts, or other operations.
#Eventually, the adversary submits two distinct chosen plaintexts
to the challenger.
#The challenger selects a bit ''b'' ∈ uniformly at random, and sends the "challenge" ciphertext ''C'' = E(PK,
) back to the adversary.
#The adversary is free to perform any number of additional computations or encryptions.
##In the ''non-adaptive'' case (IND-CCA1), the adversary may ''not'' make further calls to the decryption oracle.
##In the ''adaptive'' case (IND-CCA2), the adversary may make further calls to the decryption oracle, but may not submit the challenge ciphertext ''C''.
#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.
Indistinguishable from random noise
Sometimes we need encryption schemes in which the ciphertext string is indistinguishable from a random string by the adversary.
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.
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
Disk encryption is a technology which protects information by converting it into unreadable code that cannot be deciphered easily by unauthorized people. Disk encryption uses disk encryption software or hardware to encrypt every bit of data that g ...
such as
TrueCrypt
TrueCrypt is a discontinued source-available freeware utility used for on-the-fly encryption (OTFE). It can create a virtual encrypted disk within a file, or encrypt a partition or the whole storage device ( pre-boot authentication).
On 28 M ...
attempt to hide data in the innocent random data left over from some kinds of
data erasure
Data erasure (sometimes referred to as data clearing, data wiping, or data destruction) is a software-based method of overwriting the data that aims to completely destroy all electronic data residing on a hard disk drive or other digital media b ...
.
As another example, some kinds of
steganography
Steganography ( ) is the practice of representing information within another message or physical object, in such a manner that the presence of the information is not evident to human inspection. In computing/electronic contexts, a computer file, ...
attempt to hide data by making it match the statistical characteristics of the innocent "random"
image noise
Image noise is random variation of brightness or color information in images, and is usually an aspect of electronic noise. It can be produced by the image sensor and circuitry of a scanner or digital camera. Image noise can also originate in ...
in digital photos.
To support such
deniable encryption
In cryptography and steganography, plausibly deniable encryption describes encryption techniques where the existence of an encrypted file or message is deniable in the sense that an adversary cannot prove that the plaintext data exists.
The users ...
systems, a few cryptographic algorithms are specifically designed to make ciphertext messages indistinguishable from random bit strings.
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.
Equivalences and implications
Indistinguishability is an important property for maintaining the confidentiality of encrypted communications. However, the property of indistinguishability has in some cases been found to imply other, apparently unrelated security properties. 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. In other cases, it has been demonstrated that indistinguishability can be combined with certain other definitions, in order to imply still other useful definitions, and vice versa. The following list summarizes a few known implications, though it is by no means complete.
The notation
means that property A implies property B.
means that properties A and B are ''equivalent''.
means that property A does not necessarily imply property B.
* IND-CPA
semantic security under CPA.
* NM-CPA (
non-malleability under chosen plaintext attack)
IND-CPA.
* NM-CPA (
non-malleability under chosen plaintext attack)
IND-CCA2.
* NM-CCA2 (
non-malleability under adaptive chosen ciphertext attack)
IND-CCA2.
See also
*
Distinguishing attack
In cryptography, a distinguishing attack is any form of cryptanalysis on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data. Modern symmetric-key ciphers are specifically designed to be immune to ...
*
Computational indistinguishability
In computational complexity and cryptography, two families of distributions are computationally indistinguishable if no efficient algorithm can tell the difference between them except with negligible probability.
Formal definition
Let \scriptstyl ...
*
Chosen ciphertext attack
A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the hidd ...
*
Adaptive chosen ciphertext attack
An adaptive chosen-ciphertext attack (abbreviated as CCA2) is an interactive form of chosen-ciphertext attack in which an attacker first sends a number of ciphertexts to be decrypted chosen adaptively, and then uses the results to distinguish a tar ...
References
*
{{Cryptography navbox
Theory of cryptography
Cryptography