1
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.