Semantic security
Encyclopedia
Semantic security is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded
adversary
to derive significant information about a message (plaintext) when given only its ciphertext
and the corresponding public encryption key. Semantic security considers only the case of a "passive" attacker, i.e., one who generates and observes ciphertexts using the public key and plaintexts of her choice. Unlike other security definitions, semantic security does not consider the case of chosen ciphertext attack (CCA
), where an attacker is able to request the decryption of chosen ciphertexts, and many semantically-secure encryption schemes are demonstrably insecure against chosen ciphertext attack. Consequently, semantic security is now considered an insufficient condition for securing a general-purpose encryption scheme.
The notion of semantic security was first put forward by Goldwasser
and Micali
in 1982. However, the definition they initially proposed offered no straightforward means to prove the security of practical cryptosystems. Goldwasser/Micali subsequently demonstrated that semantic security is equivalent to the another definition of security called ciphertext indistinguishability
. This later definition is more common than the original definition of semantic security because it better facilitates proving the security of practical cryptosystems.
Indistinguishability under Chosen Plaintext Attack (IND-CPA) is commonly defined by the following game
:
The underlying cryptosystem
is IND-CPA (and thus semantically secure under chosen plaintext attack) if the adversary cannot determine which of the two messages was chosen by the oracle, with probability significantly greater than
(the success rate of random guessing). Variants of this definition define indistinguishability under chosen ciphertext attack and adaptive chosen ciphertext attack (IND-CCA, IND-CCA2).
Because the adversary possesses the public encryption key in the above game, a semantically secure encryption scheme must by definition be probabilistic
, possessing a component of randomness
; if this were not the case, the adversary could simply compute the deterministic encryption of
and 
and compare these encryptions with the returned ciphertext 
to successfully guess the oracle's choice.
Semantically secure encryption algorithms include Goldwasser-Micali
, El Gamal and Paillier. These schemes are considered provably secure
, as their semantic security can be reduced to solving some hard mathematical problem (e.g., Decisional Diffie-Hellman
or the Quadratic Residuosity Problem
). Other, non-semantically-secure algorithms such as RSA, can be made semantically secure (under stronger assumptions) through the use of random encryption padding schemes such as Optimal Asymmetric Encryption Padding
(OAEP).
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
adversary
Adversary (cryptography)
In cryptography, an adversary is a malicious entity whose aim is to prevent the users of the cryptosystem from achieving their goal...
to derive significant information about a message (plaintext) when given only its ciphertext
Ciphertext
In cryptography, ciphertext 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 that is unreadable by a human or computer without the proper cipher...
and the corresponding public encryption key. Semantic security considers only the case of a "passive" attacker, i.e., one who generates and observes ciphertexts using the public key and plaintexts of her choice. Unlike other security definitions, semantic security does not consider the case of chosen ciphertext attack (CCA
CCA
CCA can refer to:*ICAO callsign for Air China*California Charter Academy*California College of the Arts*California Culinary Academy*Canadian Canoe Association*Canadian Cascade Arc*Canadian Cat Association*Canadian Centre for Architecture...
), where an attacker is able to request the decryption of chosen ciphertexts, and many semantically-secure encryption schemes are demonstrably insecure against chosen ciphertext attack. Consequently, semantic security is now considered an insufficient condition for securing a general-purpose encryption scheme.
The notion of semantic security was first put forward by Goldwasser
Shafi Goldwasser
Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:...
and Micali
Silvio Micali
Silvio Micali is an Italian-born computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in MIT's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of cryptography and information...
in 1982. However, the definition they initially proposed offered no straightforward means to prove the security of practical cryptosystems. Goldwasser/Micali subsequently demonstrated that semantic security is equivalent to the another definition of security called ciphertext indistinguishability
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...
. This later definition is more common than the original definition of semantic security because it better facilitates proving the security of practical cryptosystems.
Indistinguishability under Chosen Plaintext Attack (IND-CPA) is commonly defined by the following game
Game
A game is structured playing, usually undertaken for enjoyment and sometimes used as an educational tool. Games are distinct from work, which is usually carried out for remuneration, and from art, which is more often an expression of aesthetic or ideological elements...
:
- A probabilistic polynomial time-bounded adversary is given a public key, which it may use to generate any number of ciphertexts (within polynomial bounds).
- The adversary generates two equal-length messages
and 
, and transmits them to a challenge oracle along with the public key. - The challenge oracle selects one of the messages by flipping a fair coin, encrypts the message under the public key, and returns the resulting ciphertext
to the adversary.
The underlying cryptosystem
Cryptosystem
There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...
is IND-CPA (and thus semantically secure under chosen plaintext attack) if the adversary cannot determine which of the two messages was chosen by the oracle, with probability significantly greater than
(the success rate of random guessing). Variants of this definition define indistinguishability under chosen ciphertext attack and adaptive chosen ciphertext attack (IND-CCA, IND-CCA2).Because the adversary possesses the public encryption key in the above game, a semantically secure encryption scheme must by definition be probabilistic
Probabilistic encryption
Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts...
, possessing a component of randomness
Randomness
Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
; if this were not the case, the adversary could simply compute the deterministic encryption of
and and compare these encryptions with the returned ciphertext to successfully guess the oracle's choice.Semantically secure encryption algorithms include Goldwasser-Micali
Goldwasser-Micali cryptosystem
The Goldwasser–Micali cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions...
, El Gamal and Paillier. These schemes are considered provably secure
Provable security
In cryptography, a system has provable security if its security requirements can be stated formally in an adversarial model, as opposed to heuristically, with clear assumptions that the adversary has access to the system as well as enough computational resources...
, as their semantic security can be reduced to solving some hard mathematical problem (e.g., Decisional Diffie-Hellman
Decisional Diffie-Hellman assumption
The decisional Diffie–Hellman assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most notably the ElGamal and Cramer–Shoup...
or the Quadratic Residuosity Problem
Quadratic residuosity problem
The quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number...
). Other, non-semantically-secure algorithms such as RSA, can be made semantically secure (under stronger assumptions) through the use of random encryption padding schemes such as Optimal Asymmetric Encryption Padding
Optimal Asymmetric Encryption Padding
In cryptography, Optimal Asymmetric Encryption Padding is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway....
(OAEP).