Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Could a variable participant lottery system cryptographically prove that they have zero knowledge of the outcome of a draw?

Participants do not choose numbers in this lottery and winning numbers are not drawn. Instead, they simply enrol with a wager. Winners are selected by taking all wagers and building an array of 'tickets' where the number of ticket entries per participant is proportional to their wager. A random index is chosen from this array, this is the winner.

I found a similar question but the answers assume that the number of participants is fixed. I'd also like to keep the participants from having to perform bit commitment as some have suggested - for trusting participants this is a PITA.

share|improve this question
3  
A zero-knowledge proof is not a proof that the prover has no knowledge, but a proof which does not give the verifier any additional knowledge beyond what is to be proved. But this is still an interesting question. I suppose the only possible way would be to include some (big enough) entropy in the calculation which will only be available after the closing of the draw, and can't be influenced by anyone interested. –  Paŭlo Ebermann Sep 2 '12 at 21:18

2 Answers 2

As I understand it, you're asking for a protocol where every player contributes some "entropy" to the overall random mechanism, so they can be assured that nobody else gamed the system. But in such a system you would assume that every player has the opportunity to select a value giving them the best chance of winning. Assuming the players know the algorithm in use, the advantage always goes to the last participant, who would have the ability to select a number that would give them the winning selection.

For starters, let's simplify the discussion and ignore the complexities introduced by the "wagers", "participants", "tickets", and "indexes". That's all noise that covers up the root of this problem, which is that you're looking for a fair 1-out-of-N choice lottery. Whatever protocol you come up with, you can figure out how tickets are sold or who gets paid later. To make it easy for discussion, I'll assume that "player" means one entry or ticket, and that "contribution" means that player's chosen value for entropy.

What is needed is a cryptographically secure random number to be generated after the lottery is closed and all participants have made their choices.

From there, you can do anything to mix in all the player's entropy contributions to yield a single number. You could simply concatenate each contribution together, including the random number at the end, and take a SHA hash of the result. Divide the hash digest by the number of players, and the remainder gives your winning index. You could be much more complex using something like the Tor protocol, where each player's contribution is used as a key to encrypt or hash the previous player's contribution, and that hash is used to determine the next "random" player, and so on. But all these are just different ways of stirring the same pot - none of them prove the pot is fair.

The problem is these schemes don't "prove" that the secure random number was generated fairly. If I were running the lottery, I could rig the random number generator to emit a non-random value, then give my collaborator-player all the other player's values, and allow him to make the last choice. When the pre-determined non-random number appears, my collaborator wins and splits the prize with me. The algorithms chosen don't matter, as long as I let my collaborator go last.

The entire lottery and every player in it could be a sham designed to take money from one unsuspecting victim. As the crooked operator, my collaborators could include every player except one: the mark.

And if that's the case, then there is no value to allowing players to contribute entropy. It mostly provides an avenue for a collaborator to make a choice that would sway the lottery in their direction.

Ultimately, every lottery boils down to "can the lottery operator be trusted?" And that's a society problem, not a math problem.

Instead of asking the players for entropy, your best approach is to use an agreed-upon future public information source as the source of entropy for your secure random number generator. XKCD did this with "geohashing", which uses the value of the previous day's NYSE closing value as the input to a hash algorithm to come up with a random latitude / longitude. It's non-deterministic (nobody can control the value to the last penny) and everyone can do the computation for themselves to see that it was fairly computed. You'd obviously need more than one source of data, and they'd have to be pretty public to avoid tampering. Perhaps you could use something like the combined hash of each of the Dow Jones 100 values at the previous day's closing, using the DJIA as a randomizer to pick the order in which they are hashed.

share|improve this answer
    
Sounds like you might be unfamiliar with multi-party secure computation? You might want to look at distributed coin-flipping protocols. See, e.g., How to fairly select a random number for a game without trusting a third party? and how to generate a community random value and Is there some way to generate a non-predictable random number in a decentralised network?. –  D.W. Sep 7 '12 at 8:30
    
I derived two assumed requirements from his request. His remark about bit-commitment being a PITA made it seem like the parties did not want to participate in a multi-phase commitment process, so complex interaction protocols like coin-tossing were out. He also said the participants were to contribute randomness, I assumed that was because they did not trust the lottery administrator. That pretty much leaves a pseudo random algorithm with an agreed-upon future seed as the remaining approach. The only work a player might do is to verify the results, and that's optional if they trust it. –  John Deters Sep 8 '12 at 5:20

Protocols for selecting uninfluenced random numbers typically fall into two camps: random beacons and coin-tossing protocols.

A random beacon is a source of randomness that is agreed by everyone to be unpredictable. For example, you can funnel a large amount of financial data into a small random number. While you cannot prove you didn't know what the closing prices would be before they actually closed, can prove that someone who possesses such knowledge can make a lot of money. A coin-tossing protocol is a protocol where everyone chooses random numbers that are combined to form the master random number. This is what is mentioned in the other answer you found.

As you point out, both of these produce a number of predetermined length. But that is ok, once the lottery closes,

  1. Calculate the number of bits you need to select $m$ out of $n$ tickets using a standard selection algorithm (for example, you can run the Fisher–Yates shuffle until you've pulled out $m$ items). Say it takes $N$ bits.
  2. Use either a random beacon or coin-tossing protocol to generate a cryptographic seed for a pseudo-random generator (PRG).
  3. Use the PRG to generate $N$ bits and run the selection algorithm.

Note selection algorithms may be non-deterministic in the number of bits they need, so you can skip step 1 and just run the PRG until the selection has completed.

You must publish beforehand the exact protocol (selection algorithm, beacon/coin-tossing, PRG) that will be used. The only variable will be the secret seed.

share|improve this answer
    
The third camp being trusted third parties. –  Zsbán Ambrus Sep 5 '12 at 17:02

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.