Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Are the agents allowed to know $p_0$..$p_k$? –  Mike Samuel Jun 21 '12 at 18:53
    
Have you seen this? ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4232861 –  dspyz Feb 13 at 16:57

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.

share|improve this answer
2  
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 Jun 15 '12 at 19:22
1  
@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 Jun 15 '12 at 19:27
2  
I'm not convinced that is possible. –  Joe Fitzsimons Jun 15 '12 at 20:23
2  
@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 Jun 16 '12 at 20:25
2  
@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 Jun 16 '12 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.
share|improve this answer
1  
“a common random string visible to all parties but controllable by none of them” is exactly what we want to generate. –  Zsbán Ambrus Jun 16 '12 at 11:53
1  
and after somehow solving that problem once, one can universally composably $\hspace{1 in}$ solve it again (arbitrarily many times). $\:$ –  Ricky Demer Jun 16 '12 at 17:37
    
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). –  Ricky Demer Jun 16 '12 at 20:55
2  
Welcome to the site, Adam! –  Gil Kalai Jun 16 '12 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.

share|improve this answer
    
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 Jun 15 '12 at 18:35
    
No worries! Seems we're on the right track, then. –  Lev Reyzin Jun 15 '12 at 19:36
    
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 Jun 15 '12 at 19:40
7  
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/… –  Ryan Williams Jun 16 '12 at 1:23
4  
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. Feb 28 '13 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.

share|improve this answer
1  
This is already noted in Joe's answer. –  Kaveh Feb 12 at 14:43
1  
The graphic illustration is very nice! –  Gil Kalai Feb 12 at 15:16
3  
The graphics are very pretty but your answer contains nothing that isn't in the existing answers. –  David Richerby Feb 12 at 15:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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