Probabilistic encryption

To be semantically secure, i.e to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.

Suppose that the adversary knows that the plaintext is either "YES" or "NO", or has a hunch that the message might be "ATTACK AT CALAIS". Using a deterministic encryption is bad in such situations, because the adversary can simply try each possible message that he suspects the plaintext to be. The encryption algorithm must therefore incorporate randomness, ensuring that each plaintext maps into one of a large number of possible ciphertexts.

The first probabilistic encryption scheme was proposed by Goldwasser and Micali based on the hardness of the quadratic residuosity problem and had a message expansion factor equal to the public key size. Efficient probabilistic encryption algorithms are possible under the random oracle model.