(Sorry if this is well known.) I would like to give some item to one of $k$ agents, so that agent $j$ will get the item with probability $p_i$. Is there a cryptographic (or other) tool so that every agent (and even every observer) will be able to be convinced that the random drawing was indeed fair?


4 Answers 4


If I am understanding the problem correctly, it would seem to amount to public flipping a $k$-sided coin. There seem to be lots of ways to do this if you assume bit commitment. One example would be having each party generate a random integer between 0 and $k-1$, using bit commitment to publicly commit to that bit string. Then once each agent has committed, they all publicly reveal their secret integer. The winning agent is then the one indexed by the sum of the integers modulo $k$. If even one agent is honest, then the flip must be random.

Of course one problem with this is that it requires bit commitment. Information theoretic schemes for bit commitment are impossible for both classical and quantum computing (though Adrian Kent recently proposed a scheme exploiting relativity). However, secure bit commitment can be achieved with computational assumptions.

  • 2
    $\begingroup$ My problem with this approach is that if you want to convince a lot of outside observers from fairness, then each of them has to commit a bit and you must be sure that each of them will reveal the proof of their commitment. You can't just ignore the bit of an observer that does not reveal their proof because then the last observer to reveal could manipulate the lottery result by deciding whether or not to reveal his proof. $\endgroup$ Commented Jun 15, 2012 at 19:22
  • 1
    $\begingroup$ @user8067: I don't believe it is possible without interaction or trusting that at least one party is honest. The reason I say this is that if the initial randomness is actually predetermined through a conspiracy of everyone participating at that point, then the entire process is deterministic and not random. However the problem requires the process be random, so this seems to be the best you can do. $\endgroup$ Commented Jun 15, 2012 at 19:27
  • 2
    $\begingroup$ I'm not convinced that is possible. $\endgroup$ Commented Jun 15, 2012 at 20:23
  • 2
    $\begingroup$ @RickyDemer: There's not enough information in the question to tell what adversary model is applicable here. If Gil told us exactly what it's for, then it would be easier to prove whether or not a specific scheme meets his requirements. But that said, I have no doubt Gil is more than capable of checking whether or not our answers meet his needs. $\endgroup$ Commented Jun 16, 2012 at 20:25
  • 2
    $\begingroup$ @RickyDemer: It's not at all clear to me what the obvious model is for this case. It strongly depends the setup, and it's not obvious what the default assumptions should be. It's a little much to downvote and start acting like both my answer and Lev's are wrong. They don't explicitly include the caveat pointed out in Adam's answer. Note that I am -not- editing my answer, because without more information from Gil, I don't see it making sense to guess about the adversary model, and so I am leaving it as general as possible (not specifying whether or not the bit commitment need be non-maliable). $\endgroup$ Commented Jun 16, 2012 at 21:30

As other users have hinted at, this is a well-studied problem in cryptography. It is called "coin-flipping" and is a special case of multiparty computation.

What protocol does the job actually depends on the context quite a lot.

  • In the "standalone" setting, the protocol will be run in isolation, without players being involved in other protocols (or indeed, any interaction with the outside world) at the same time. There is a wonderfully thorough treatment of this in Oded Goldreich's textbook "Foundations of Cryptography" (Volume 2, I think).

Just to give an idea of how subtle it is, the "everybody commits to random values" protocol suggested by another responder is insecure if the commitment scheme you use is malleable. Nonmalleable commitment schemes do give you a secure protocol, but they are a bit complicated to design.

  • In settings where participants are involved in other concurrent protocols, you want a protocol that is composable. There are various notions of composability, but the strongest one, called universal composability, requires some additional set-up assumptions (for example, a PKI or a common random string visible to all parties but controllable by none of them). I don't know of an accessible treatment of this topic, unfortunately. But looking at a recent paper on either universal composability or nonmalleable commitment would be a good place to start.
  • 1
    $\begingroup$ “a common random string visible to all parties but controllable by none of them” is exactly what we want to generate. $\endgroup$ Commented Jun 16, 2012 at 11:53
  • 1
    $\begingroup$ and after somehow solving that problem once, one can universally composably $\hspace{1 in}$ solve it again (arbitrarily many times). $\:$ $\endgroup$
    – user6973
    Commented Jun 16, 2012 at 17:37
  • $\begingroup$ I think UC commitment is known for Registered Public Key setup (which is a stronger assumption than PKI) and multi-string setup (which is a weaker assumption than common random string). $\endgroup$
    – user6973
    Commented Jun 16, 2012 at 20:55
  • 2
    $\begingroup$ Welcome to the site, Adam! $\endgroup$
    – Gil Kalai
    Commented Jun 16, 2012 at 23:08

Note: please read the comments below. This protocol seems to have problems.

I don't know much crypto, but perhaps the following would work. Assuming the $p_j$'s are publicly known, all that's needed to determine the winner is to select a random number from [0,1].

Here's the process: Each agent selects a random vector in $\{0,1\}^b$, where $b$ is the number of bits of precision that are needed for the process. Then they all cryptography commit to their vectors using known protocols. Finally, once all the vectors are committed to, all their vectors are revealed (and checked) and XORed and the result is the random number to be used. Namely the resulting vector is the binary representation of digits past the decimal point.

Any agent can be sure the chosen random number came uniformly at random by choosing his own vector uniformly at random. For any observer to be convinced, they have to trust that at least one agent followed the protocol, but if none did, I guess nobody really wanted a fair lottery to begin with.

  • $\begingroup$ Sorry Lev, I've just noticed your answer. When I started writing an answer there was nothing here, but we both seem to have come up with very similar answers. $\endgroup$ Commented Jun 15, 2012 at 18:35
  • $\begingroup$ No worries! Seems we're on the right track, then. $\endgroup$
    – Lev Reyzin
    Commented Jun 15, 2012 at 19:36
  • $\begingroup$ Yes, actually I think there are a lot of papers on this in the context of coin flipping, but I don't really know that literature well enough to give a proper answer based on it. $\endgroup$ Commented Jun 15, 2012 at 19:40
  • 7
    $\begingroup$ The earliest reference I know is: M. Blum. Coin Flipping By Telephone. CRYPTO 1981: 11-15. Can be downloaded at dm.ing.unibs.it/giuzzi/corsi/Support/papers-cryptography/… $\endgroup$ Commented Jun 16, 2012 at 1:23
  • 4
    $\begingroup$ There's a standard attack, if you use standard bit commitment schemes (e.g., hashing). Let's consider the case with two parties, Alice and Bob, where Alice goes first. After Alice broadcasts her commitment, Bob can copy it. After Alice opens her commitment, Bob can open his the same now. Now their random vectors are equal, so they xor to zero -- Bob was able to force the final value to zero, a contradiction of the requirement for fairness. $\endgroup$
    – D.W.
    Commented Feb 28, 2013 at 2:18

Passive observers can't verify that the drawing wasn't staged. Inputs into pseudorandom process can be chosen to give desired result.

However if the observer can supply a random number that he knows is random AND make sure that other agents won't change their inputs afterwards (because they could compensate his effect with their inputs), then he can be sure that the result was indeed random.

This requires commitment scheme which we don't know any that is mathematically proven to be secure but in practice can be realized using secure hash (such as SHA3).

Consider this example:

enter image description here

I've made an example implementation. You can see it live here: https://mrogalski.eu/cl/ or check sources on GitHub.

  • 1
    $\begingroup$ This is already noted in Joe's answer. $\endgroup$
    – Kaveh
    Commented Feb 12, 2014 at 14:43
  • 1
    $\begingroup$ The graphic illustration is very nice! $\endgroup$
    – Gil Kalai
    Commented Feb 12, 2014 at 15:16
  • 3
    $\begingroup$ The graphics are very pretty but your answer contains nothing that isn't in the existing answers. $\endgroup$ Commented Feb 12, 2014 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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