### Question 36. What is Probabilistic Encryption?

Probabilistic encryption, discovered by Goldwasser and Micali
[GM84],
is a design approach for encryption where a message is encrypted into one
of many possible ciphertexts (not just a single ciphertext as in deterministic
encryption), in such a way that it is provably as hard to obtain partial
information about the message from the ciphertext, as it is to solve some
hard problem. In previous approaches to encryption, even though it was
not always known whether one could obtain such partial information, neither
was it proved that one could not do so.

A particular example of probabilistic encryption given by Goldwasser
and Micali operates on "bits" rather than "blocks"
and is based on the *quadratic residuosity problem*. The problem is
to find whether an integer *x* is a square modulo a composite integer
*n*. (This is easy if the factors of *n* are known, but presumably
hard if they are not.) In their example, a "0" bit is encrypted
as a random square, and a "1" bit as a non-square; thus it is
as hard to decrypt as it is to solve the quadratic residuosity problem.
The scheme has substantial message expansion due to the bit-by-bit encryption
of the message. Blum and Goldwasser later proposed an efficient probabilistic
encryption scheme with minimal message expansion [BG85].