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.