Could a variable participant lottery system cryptographically prove that they ha
ID: 650329 • Letter: C
Question
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.
Explanation / Answer
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,
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