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.