Semantic security
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 generates two equally-sized messages, <math>m_1<math> and <math>m_2<math>, and transmits them to an encryption oracle along with a public encryption key. This oracle chooses one message at random, encrypts it using the 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.
