In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, a semantically secure
cryptosystem is one where only negligible information about the
plaintext
In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted.
Overview
With the advent of com ...
can be feasibly extracted from the
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 ...
. Specifically, any
probabilistic, polynomial-time algorithm (PPTA) that is given the ciphertext of a certain message
(taken from any distribution of messages), and the message's length, cannot determine any partial information on the message with probability non-negligibly higher than all other PPTA's that only have access to the message length (and not the ciphertext).
[ S. Goldwasser and S. Micali]
Probabilistic encryption & how to play mental poker keeping secret all partial information
Annual ACM Symposium on Theory of Computing, 1982. This concept is the computational complexity analogue to
Shannon's concept of
perfect secrecy. Perfect secrecy means that the ciphertext reveals no information at all about the plaintext, whereas semantic security implies that any information revealed cannot be feasibly extracted.
[ Goldreich, Oded. Foundations of Cryptography: Volume 2, Basic Applications. Vol. 2. Cambridge university press, 2004.]
History
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 another definition of security called
ciphertext indistinguishability under chosen-plaintext attack.
[ S. Goldwasser and S. Micali]
Probabilistic encryption
Journal of Computer and System Sciences, 28:270-299, 1984. This latter definition is more common than the original definition of semantic security because it better facilitates proving the security of practical cryptosystems.
Symmetric-key cryptography
In the case of
symmetric-key algorithm cryptosystems, an adversary must not be able to compute any information about a plaintext from its ciphertext. This may be posited as an adversary, given two plaintexts of equal length and their two respective ciphertexts, cannot determine which ciphertext belongs to which plaintext.
Public-key cryptography
For an
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 ...
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
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 ...
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
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 ...
(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.
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 commonly defined by the following experiment:
# A random pair
is generated by running
.
# A probabilistic polynomial time-bounded adversary is given the 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 (selecting a random bit
), encrypts the message
under the public key, and returns the resulting ''challenging ciphertext''
to the adversary.
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
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 ...
(
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
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...
; 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,
ElGamal and
Paillier. These schemes are considered
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 ...
, as their semantic security can be reduced to solving some hard mathematical problem (e.g.,
Decisional Diffie-Hellman or the
Quadratic Residuosity Problem The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not.
Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...
). Other, semantically insecure 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).
References
Theory of cryptography