# What is the advantage of a probabilistic PKC over a traditional PKC?

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?

• A non-probabilistic key generation algorithm always outputs the very same key because key generation algorithms don't take inputs. – SEJPM Apr 24 '17 at 20:01
• @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? – tpm900 Apr 24 '17 at 20:03
• Note that the term 'public key cryptosystem' includes signature algorithms; you can have both secure deterministic signature algorithms and secure randomized ones. – poncho Apr 24 '17 at 20:42

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.