While reading through a textbook, I came across the idea of a probabilistic public key cryptosystem, which uses a probabilistic TM to generate the public encryption and private decryption algorithm; it is possible the encryption algorithm is probabilistic. If the encryption algorithm were not probabilistic, would the PPKC have an advantage of a traditional, non-probabilistic PKC? Can a traditional PKC offer a probabilistic encryption algorithm?

  • $\begingroup$ A non-probabilistic key generation algorithm always outputs the very same key because key generation algorithms don't take inputs. $\endgroup$ – SEJPM Apr 24 '17 at 20:01
  • $\begingroup$ @SEJPM so the advantage of PPKC is that the encryption algorithm can produce different results for the same input, reducing the possibility the encryption of identical messages is repeated? $\endgroup$ – tpm900 Apr 24 '17 at 20:03
  • 1
    $\begingroup$ Note that the term 'public key cryptosystem' includes signature algorithms; you can have both secure deterministic signature algorithms and secure randomized ones. $\endgroup$ – poncho Apr 24 '17 at 20:42

Every secure public key cryptosystem must have a probabilistic encryption algorithm.

Suppose this was not the case and consider the usual IND-CPA game.
An attacker can now win this game with probability 1 as follows:

  1. He chooses two distinct messages $m_1,m_2$ at his liking and submits them to the challenger.
  2. The challenger chooses a bit $b\in\{0,1\}$ uniformly at random and answers with $c'=c_b=E_{pk}(m_b)$.
  3. The adversary computes $c_0=E_{pk}(m_0)$, if $c_0=c'$ he outputs 0, otherwise 1.
  4. As the encryption algorithm is non-probabilistic, ie deterministic his choice for $b$ is right 100% of the time because he can be sure to always to the same value as the challenger.

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.