[Cryptography] A Scheme for Verifiable Lottery

[Yunxiang Li]

On Mon, 2020-11-30 at 17:04 -0800, John-Mark Gurney wrote:
> No, the easier way to do this is have everyone generate a 128-bit value.
> The organizer XOR's everyone's contribution together, then using HMAC
> to extract the final selection/results of the lottery.  This could be
> a simple, select out of n algorithm where n is the number of participants.

If taking this approach it has to use a commitment scheme, or the orgainizer can
change the result trivialy. It would mean joinging the lottery takes more effort
tho, which is undesirable. Ideally only the orgainizer and someone that want to
verify the result need to do extra work.

Since we only really need one honest participants, which can be the people that
want to verify the result. maybe we can do something like the following.

The orgainizer commits to a random string as fallback (in case no one wanted to
verify), and participants that wishes to verify commits to a random string as
well.
For each participant, the orgainizer gives them an anonymous identifier that is
the salted hash of their username, for those that commited, the orgainizer
publishes the anonymous identifier with their commitment.
After the list is compiled, everyone that did commit a string reveals their
answer, which all get XORed together and used as the key to a MAC function.
Using the MAC function each participants gets their score (the MAC tag of their
anonymous identifier), and the lowest N wins.

The winner still needs to have their identity revealed, and the salt as well, to
guard against fake entries. It is of course possible to create fake account as
well, but I don't think it's possible to stop those types of attacks, be it a
real lottery or a virtual one :(

> As for the list of participants, the name doesn't need to be identifiable,
> it can be a UUID or another anonymous identifier, allowing each
> participant to ensure that their contribution was used in the results.

IDK why I haven't thought about using an anonymous identifier to get around the
whole publish the participants problem. lol