<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-06-15T19:22:05.253Z
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.
Zsbán Ambrus
CC BY-SA 3.0
2012-06-15T19:27:50.080Z
@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.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-15T19:49:00.430Z
(user8067 here) okay, but I'd still like a way where observers have to commit, but any observer can choose not to reveal their commit proof (or otherwise fail to follow the procedure) yet all other observers will be convinced the lottery is fair.
Zsbán Ambrus
CC BY-SA 3.0
2012-06-15T20:23:54.417Z
I'm not convinced that is possible.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-16T20:25:02.260Z
@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.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-16T21:30:23.840Z
@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).
Joe Fitzsimons
CC BY-SA 3.0
2012-06-17T14:42:27.997Z
@RickyDemer: Well, secure communications channels seemed to me like a reasonable thing to assume, but maybe not. It really depends on what Gil wants this for.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-15T18:32:54.080Z
2012-06-15T18:32:54.080Z
Joe Fitzsimons
<p><strong>Note: please read the comments below.  This protocol seems to have problems.</strong></p>

<hr>

<p>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].  </p>

<p>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.  </p>

<p>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.</p>

CC BY-SA 3.0
2012-06-15T18:35:28.197Z
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.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-15T19:36:54.203Z
No worries! Seems we're on the right track, then.
Lev Reyzin
CC BY-SA 3.0
2012-06-15T19:40:17.210Z
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.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-16T01:23:41.440Z
The earliest reference I know is: M. Blum. Coin Flipping By Telephone. CRYPTO 1981: 11-15. Can be downloaded at http://dm.ing.unibs.it/giuzzi/corsi/Support/papers-cryptography/Coin_flipping.pdf
Ryan Williams
CC BY-SA 3.0
2012-06-16T18:18:11.263Z
That makes sense. However, I don't think Gil's question asked about adversaries attacking the lottery, etc.
Lev Reyzin
CC BY-SA 3.0
2012-06-16T18:29:44.103Z
Sorry, I mistyped.  Of course if everyone were honest there'd be no question.  But what types of attacks a system should prevent is unclear to me.  Also, I don't really see a problem -- why not just use a non-malleable commitment scheme?
Lev Reyzin
CC BY-SA 3.0
2012-06-16T18:48:09.400Z
Thinking about it again, I don't see why.  If everyone first commits to their vectors, anyone honest can make sure his vector wasn't tampered with.  Then, when the vectors are revealed abd XORed, it's too late to tamper.  Where exactly is the problem?
Lev Reyzin
CC BY-SA 3.0
2013-02-28T02:18:03.507Z
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.
D.W.
CC BY-SA 3.0
2013-02-28T03:22:41.670Z
@D.W. Thanks for the clear explanation -- that makes sense.
Lev Reyzin
CC BY-SA 3.0
2012-06-15T18:21:07.230Z
2013-02-28T15:49:35.697Z
2013-02-28T15:49:35.697Z
Lev Reyzin
<p>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. </p>

<p>What protocol does the job actually depends on the context quite a lot. </p>

<ul>
<li>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).</li>
</ul>

<p>Just to give an idea of how subtle it is, the "everybody commits to random values" protocol suggested by another responder is <em>insecure</em> 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. </p>

<ul>
<li>In settings where participants are involved in other concurrent protocols, you want a protocol that is <em>composable</em>. There are various notions of composability, but the strongest one, called <em>universal composability</em>, 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. </li>
</ul>

CC BY-SA 3.0
2012-06-16T11:53:04.407Z
“a common random string visible to all parties but controllable by none of them” is exactly what we want to generate.
Zsbán Ambrus
CC BY-SA 3.0
2012-06-16T23:08:45.370Z
Welcome to the site, Adam!
Gil Kalai
CC BY-SA 3.0
2012-06-16T02:32:56.027Z
2012-06-16T02:32:56.027Z
Adam Smith
<p>Passive observers can't verify that the drawing wasn't staged. Inputs into pseudorandom process can be chosen to give desired result.</p>

<p>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.</p>

<p>This requires <em>commitment scheme</em> 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).</p>

<p>Consider this example:</p>

<p><img src="https://i.sstatic.net/n9C6l.png" alt="enter image description here"></p>

<p>I've made an example implementation. You can see it live here: <a href="https://mrogalski.eu/cl/" rel="nofollow noreferrer" title="Crypto Lottery">https://mrogalski.eu/cl/</a> or check sources on <a href="https://github.com/mafik/crypto-lottery" rel="nofollow noreferrer" title="Crypto Lottery - GitHub">GitHub</a>.</p>

CC BY-SA 3.0
2014-02-12T14:43:45.923Z
This is already noted in Joe's answer.
Kaveh
CC BY-SA 3.0
2014-02-12T15:16:11.750Z
The graphic illustration is very nice!
Gil Kalai
CC BY-SA 3.0
2014-02-12T15:31:48.337Z
The graphics are very pretty but your answer contains nothing that isn't in the existing answers.
David Richerby
CC BY-SA 3.0
2014-02-12T14:26:19.460Z
2014-02-12T14:26:19.460Z
Marek Rogalski
<p>(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?</p>

CC BY-SA 3.0
2012-06-21T18:53:24.000Z
Are the agents allowed to know $p_0$..$p_k$?
Mike Samuel
CC BY-SA 3.0
2014-02-13T16:57:10.857Z
Have you seen this? http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4232861
dspyz
<cr.crypto-security>
A lottery that you can be convinced that it is fair
Gil Kalai
# A lottery that you can be convinced that it is fair

(Asked by: username_0 on 2012-06-15)

(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?

**Tags:** cr.crypto-security
> **Comments:**
> **username_1**: Are the agents allowed to know $p_0$..$p_k$?  
> **username_2**: Have you seen this? http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4232861  

---

## 4 answers

### Answer by username_3 on 2012-06-15. Score: 19

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.

> **Comments:**
> **username_4**: 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.  
> **username_3**: @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.  
> **username_4**: (user8067 here) okay, but I'd still like a way where observers have to commit, but any observer can choose not to reveal their commit proof (or otherwise fail to follow the procedure) yet all other observers will be convinced the lottery is fair.  
> **username_3**: I'm not convinced that is possible.  
> **username_3**: @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.  
> **username_3**: @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).  
> **username_3**: @RickyDemer: Well, secure communications channels seemed to me like a reasonable thing to assume, but maybe not. It really depends on what Gil wants this for.  

---

### Answer by username_8 on 2012-06-16. Score: 15

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.

> **Comments:**
> **username_4**: “a common random string visible to all parties but controllable by none of them” is exactly what we want to generate.  
> **username_0**: Welcome to the site, Adam!  

---

### Answer by username_5 on 2012-06-15. Score: 11

**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.

> **Comments:**
> **username_3**: 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.  
> **username_5**: No worries! Seems we're on the right track, then.  
> **username_3**: 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.  
> **username_6**: The earliest reference I know is: M. Blum. Coin Flipping By Telephone. CRYPTO 1981: 11-15. Can be downloaded at http://dm.ing.unibs.it/giuzzi/corsi/Support/papers-cryptography/Coin_flipping.pdf  
> **username_5**: That makes sense. However, I don't think Gil's question asked about adversaries attacking the lottery, etc.  
> **username_5**: Sorry, I mistyped.  Of course if everyone were honest there'd be no question.  But what types of attacks a system should prevent is unclear to me.  Also, I don't really see a problem -- why not just use a non-malleable commitment scheme?  
> **username_5**: Thinking about it again, I don't see why.  If everyone first commits to their vectors, anyone honest can make sure his vector wasn't tampered with.  Then, when the vectors are revealed abd XORed, it's too late to tamper.  Where exactly is the problem?  
> **username_7**: 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.  
> **username_5**: @D.W. Thanks for the clear explanation -- that makes sense.  

---

### Answer by username_9 on 2014-02-12. Score: -3

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](https://i.sstatic.net/n9C6l.png)

I've made an example implementation. You can see it live here: [https://mrogalski.eu/cl/](https://mrogalski.eu/cl/ "Crypto Lottery") or check sources on [GitHub](https://github.com/mafik/crypto-lottery "Crypto Lottery - GitHub").

> **Comments:**
> **username_10**: This is already noted in Joe's answer.  
> **username_0**: The graphic illustration is very nice!  
> **username_11**: The graphics are very pretty but your answer contains nothing that isn't in the existing answers.  

---

