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. To be semantically secure, that is, 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 plaintext might be "ATTACK AT CALAIS". Using a deterministic encryption algorithm is bad in either of these situations, because the adversary can simply try encrypting 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.
Intuitively, probabilistic encryption can be thought of as padding the plaintext with a random string before encrypting with a deterministic algorithm. Conversely, decryption involves applying a deterministic algorithm and ignoring the random padding. While this is not in general secure, it can be made secure with techniques such as Optimal Asymmetric Encryption Padding.
Example of probabilistic encryption using any trapdoor permutation:
This is inefficient because only a single bit is encrypted. In other words, the message expansion factor is equal to the public key size.
Example of probabilistic encryption in the random oracle model:
