Probabilistic Encryption

[References to ``the paper'' in this section are to ``Probabilistic Encryption,'' in Journal of Computer & System Sciences 28, pp. 270-299. I have also used Primality and Cryptography, by E. Kranakis]

So far, the public key systems have been functions $f$ such that the message $M$ presumably cannot be computed from the encoding $f(M)$. A further concern arises as to whether, even if the adversary cannot identify $M$ exactly, he may be able to obtain some partial information about $M$, for example tell whether $M$ 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, $M_1$ or $M_2$. Since we have been assuming that the function $f$ is easy to calculate, all the adversary needs to do is compare $f(M_1)$ and $f(M_2)$ with the ciphertext.

Probabilistic encryption is a system designed to avoid these problems. Instead of $f(M)$ being a single number, the calculation of $f(M)$ involves the sender doing some things randomly during the calculation, so that $M$ 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.