# 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. Apr 24, 2017 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? Apr 24, 2017 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. Apr 24, 2017 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.