Semantic security - Definition

An asymmetric key encryption algorithm is considered semantically secure if it is not possible for a computationally-bounded adversary to derive significant information about a plaintext given only its ciphertext and the corresponding public encryption key. Semantic security is commonly defined by a game in which an adversary is given a public key, generates two equally-sized messages <math>m_0<math> and <math>m_1<math>, and transmits them to an encryption oracle. This oracle chooses one of the messages at random, encrypts it under the public key, and returns the resulting ciphertext <math>c<math> to the adversary. The underlying cryptosystem is semantically secure if the adversary cannot determine which of the two messages was chosen by the oracle, with probability significantly greater than <math>1/2<math>.

Because the adversary possesses the public encryption key, 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 <math>m_1<math> and <math>m_2<math> and compare the result with the returned ciphertext <math>c<math>.

Semantically secure encryption algorithms include El Gamal and Paillier. Many 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 OAEP.