[Cryptography] A Scheme for Verifiable Lottery

[Peter Fairbrother]

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
> impossible.

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.