# 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 algorithms.

How is it different from deterministic encryption algorithms ? How can the output of probabilistic algorithm be different for same pair of plaintext 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.

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.