Probabilistic Encryption

Deterministic public key cryptosystems can be modeled like so:

f is the encryption function, where M is a message.

Therefore, the encrypted payload is f(M), which is deterministic (I can cheaply verify that the payload is M if I have f(M) and they are equal.

This is prone to partial information leaks and other attacks — let’s say you know that M is either M1 or M2. In a deterministic cryptosystem, you can apply f to M1 and M2 and figure out whether M is M1 or M2 cheaply.

To mitigate against that, probabilistic encryption involves sending a random number along with the payload, so the function looks like f(rand(), M) which almost never encrypts the same payload the same.