# What is the meaning of "probabilistic encryption algorithm"?

I am learning cryptography by myself, and I am not able to understand the meaning of "probabilistic encryption algorithm".

How is it different from "deterministic encryption algorithm"? How can the output of a probabilistic algorithm be different for the same pair of plain text and key when used two different times? Doesn't the cipher text depend only on key and plain text?

To clear your doubt, consider a random key of length $l(n)$ where l in a polynomial in the size of message bits $n$. This is the source of stochastic/probabilistic/randomization to the polynomial encryption algorithm.

As an example, consider a one-time pad with $l(n) = 3*n$ key length and a message of 2 bits ($n = 2$).

Let the random bits of the $k = 110100$ and $m$ = 01

then $Enc_k(m)$ = 01 XOR 11 = 10 at first.

If you choose to encrypt m again,

then $Enc_k(m)$ = 01 XOR 01 = 00

Thus, the cipher-text has changed. This is a probabilistic polynomial time encryption algorithm.

If you use this 6 bit key repeatedly on a message of size 6 bits and you use it every time to encrypt $m$ using the one time pad. Then you will get a deterministic polynomial time encryption algorithm. Note how the key has become non random and hence the probabilistic becomes deterministic.

• This is wrong. A probabilistic encryption scheme is still probabilistic with the same key, e.g. ElGamal. The following are examples, which are not probabilistic: OTP, blockciphers in ECB mode, RSA. A probabilistic scheme requires some other source of randomness, which influences the ciphertext.
– tylo
Sep 16, 2019 at 6:13

Informally, in probabilistic encryption random values are used to encrypt a message. Thus, each time we encrypt a message we pick a fresh random value; as a result if we encrypt the same message twice we would get different encrypted value (or ciphertext).This means that the ciphertext does not depend only on key and plaintext.

How can the output of a probabilistic algorithm be different for the same pair of plain text and key when used two different times?

The probabilistic algorithm makes calls to a random number generator and uses that generator's output in such a way that the algorithm's output depends on the random numbers as well as the plaintext and key. If you're scratching your head and thinking "Really, is that all there is to it?" then you've understood it.

One incrementally more elaborate way to think of deterministic vs. probabilistic algorithms is to picture two different kinds of abstract machine:

1. A deterministic machine, where every instruction call produces results that are uniquely determined by the values of their invocation arguments;
2. A probabilistic machine, where some instructions produce random results—results that cannot be uniquely predicted from the invocation arguments.

You can also think of a probabilistic machine as one that duplicates the design of some deterministic one but, in addition, has an instruction that produces a fresh random bit each time it's called.

A deterministic algorithm is just one that can run on a deterministic machine. A probabilistic one is just one that requires a probabilistic machine.