[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Cryptography] A Scheme for Verifiable Lottery

On 25/11/2020 03:31, Yunxiang Li wrote:
Post the following info:
   A Lottery name, this needs to be unique each time
   MAC tag of a chosen "lucky number"
   The number of winners
When participants sign-up, they are given some sort of proof for joining,
"Lottery name + username" signed with the organizer's keypair (for example)
Calculate participants' score from their unique username
   score = min(hash(1, <lottery name>, <username>),
               hash(2, <lottery name>, <username>),
               hash(<lucky number>, <lottery name>, <username>

Winners are the participants with the lowest score.
Announce the winner, the lucky number with the MAC key used to generate the tag

The rationale for the repeated hashing is that since the randomness are picked
by the organizer, there's no way to stop them from favoring someone by trying
possible lucky numbers. Therefore with this scheme, they would need to give
everyone else at least the same number of tries, making picking favorites

IIUC that doesn't work - but I don't understand precisely what you are saying [1]. I don't see how the repeated [2] hashing gains you anything (and it sure doesn't make it fast to compute, unless you have hardware hashers).

But the scheme is broken anyway. Here is one attack:

N tickets sold. Organiser picks N trial usernames and test hashes them with genuine lucky number etc.

Organiser's shill then buys the test with the lowest score and discards the other tests. Shill has a 50% chance of winning.

I may be misunderstanding something, you are not clear, but afaict the organiser publishes the hash of the lucky number then reveals it after the entries are closed. The organiser then has the advantage of knowing the lucky number while entries can be bought, and can translate that into free tries.

If not, the lucky number serves no purpose I can see. If the lucky number is public then the public can try new usernames to find one which hashes to a low number.

Peter Fairbrother

[1] this scheme is not well-described. suppose I want to calculate the second hash - is the username different? do I calculate a series of hashes for each entrant?

[2] what you have described is not repeated hashing as far as I can tell, it is just lots of different hashes. The results of the previous hash are not used to calculate the next hash.

The cryptography mailing list
cryptography AT metzdowd.com