### 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.