Probabilistic Encryption

So far, the public key systems have been functions such that
the message presumably cannot be computed from the encoding .
A further concern arises as to whether, even if the adversary cannot
identify exactly, he may be able to obtain some partial information
about , for example tell whether is an even number, a square,
a power of 2, etc.

An extreme case of this would be a scenario
in which the adversary knows the message is one of two possibilities,
or . Since we have been assuming that the function is
easy to calculate, all the adversary needs to do is compare and
with the ciphertext.

Probabilistic encryption is a system designed to avoid these problems.
Instead of being a single number, the calculation of involves
the sender doing some things randomly during the calculation, so that
has many different encryptions. Indeed, the probability should be very
close to 1 that if the same message is sent twice, the encryptions should
be different.

- The Goldwasser-Micali encryption system
- Weak laws of large numbers
- The magic of sampling
- Determining algorithm performance by sampling
- Two versions of QRA
- Knowing a pseudo-square does not help much
- The inability to distinguish two plaintexts
- Semantic Security
- How to play poker over the telephone

2002-12-14