I'm reading a Definition of Public Key Encryption and here say:

... Enc is a (possibly) probabilistic polynomial time encryption algorithm which takes as input a public key $pk$, a $m\in M$ and random coins $r$, and outputs a ciphertext $c\in C$.

But in other papers, there is no mention of coins $r$.

Can you give me examples of PKC encrytion algorithms with coins?


All textbook PKC systems are never applied as they are described. Take e.g: RSA. There is a random padding technique that plays the role of the coins. The coins make the scheme probabilistic. For the same reason a block cipher which is instatiated as a pseudorandom permutations takes as input an instatiation vector IV. OAEP is a commonly used random encoding scheme before applying RSA on your data.


Informally, we often say that a probabilistic algorithm is allowed to "toss a coin". Technically, we say that the algorithm has a random tape containing bits that have been chosen randomly. This random tape contains its "coin tosses" or just "coins".

Of course, any such algorithm can also be turned into a deterministic algorithm that in addition to its normal inputs also takes a bit string (of suitable length) as input, and uses this bit string as its random tape, or "coins". If we run this alternative algorithm with a random bit string as input, we get the exact same effect as we do when running the original algorithm (that has its own per-execution random tape).

Which means that any public key cryptosystem with a probabilistic encryption algorithm uses "coins", but it may not be described in those terms.

In cryptography, it is sometimes convenient to do use this alternative representation. For instance, if we have a public key cryptosystem with an encryption algorithm $\mathcal{E}(ek, m; r)$, we can turn this into a commitment scheme. To commit to a message $m$, choose a random string $r$ and compute the commitment $c$ as $\mathcal{E}(ek, m; r)$. To open the commitment, reveal $m$ and $r$.

If you use the traditional formulation of $\mathcal{E}$ as a probabilistic algorithm, the construction doesn't make sense.

Note that I've skipped some rather important details about key generation in the example.

  • $\begingroup$ This answer doesn't follow the question. You don't give any PKC that tosses coins. $\endgroup$ – curious Nov 3 '13 at 19:09
  • $\begingroup$ Pick any secure public key cryptosystem. It tosses coins. (It may not be described in those terms, but it can be.) I'll amend the answer. $\endgroup$ – K.G. Nov 3 '13 at 19:16
  • $\begingroup$ I don't disagree that any PKC does toss coins. But the question is different $\endgroup$ – curious Nov 3 '13 at 19:22
  • $\begingroup$ @curious take ElGamal encryption, there you toss coins in order to generate your ephemeral (randomizer) $k$. Recall, if we have ElGamal in $Z_p^*$ and let $y=g^x$ the public key, then we encrypt a message $m$ by computing $(c_1,c_2)=(g^k,my^k)$ with $k$ randomly selected from $Z_p$. This can be viewed as "coin tosses". $\endgroup$ – DrLecter Nov 3 '13 at 19:36
  • $\begingroup$ Sorry i think you don't understand what i am saying.The question says describe me a PKC that toss coins doesn't say re-explain me the $\endgroup$ – curious Nov 3 '13 at 19:47

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.