Cryptography
public-key zero-knowledge-proofs random-number-generator
Updated Sat, 10 Sep 2022 19:05:18 GMT

Is there a cryptographic algorithm that can make a "lottery ticket"?


With public-key cryptography, I know Alice can "seal" a message that only Bob can open. But in that case, Alice knows the message that she is sealing.

What if Alice wants to seal a random number which she doesn't know? Could she seal it such that only Bob can determine it, not Alice?

Here, more specifically, is the kind of situation I'm wondering about:
Say the random number is from a uniform distribution 1 through 10. Alice seals an envelope containing the random number, without knowing what it is. While she doesn't know the number, she can be sure that it is one of the options 1-10 with uniform probability. Bob (and only Bob) can unseal it, and he can be sure that he's the only person who can. So when he opens it, he knows he is the first and only person to see what random number was generated by Alice. Then he can tell Alice what he got. And provide verification, so that Alice is then able to verify that Bob is being truthful about the number he claimed he got.

Bob should have cryptographic assurance that:

  1. He was the first to "scratch off" (identify) the randomly generated number.
  2. The number was fairly generated from the [1..10] uniform distribution.

Is such a cryptographic algorithm known or possible?


EDIT: Thank you for all the helpful discussion and feedback!

To take this question one step further: is there a way that Alice can prepare and send the "ticket" to Bob using only one message?

Meaning, basically: Can Alice prepare such a ticket using only Bob's public key?

Or, more exactly: Alice, in preparing the ticket to send to Bob, can use Bob's public key, or other previously known information -- but she can generate multiple different tickets to send without needing Bob to contact her each time a new one is generated. Only one packet -- the one from Alice to Bob, would be needed to send Bob one ticket.

Is an algorithm possible to create the "lottery ticket" with this additional "single-packet" limitation?




Solution

Bob picks an integer $n$ between 0 and 9 (inclusive), and a uniformly random 128-bit blinding factor $b$. Bob informs Alice of the hash commitment $c=H(n \mathbin\| b)$. $H()$ is a cryptographically secure hash, such as SHA256. $n$ and $b$ should be represented in fixed-bit-length form inside the hash concatenation.

Alice picks a uniformly random integer $n'$ between 0 and 9 (inclusive). She informs Bob of $n'$.

Bob can now calculate his lottery ticket value as $v = 1 + ((n+n') \operatorname{mod} 10)$.

When Bob wishes to announce $v$, he also needs to announce his values $n$ and $b$ so that the world can verify that those values match his commitment $c$.

If Alice only knows Bob's public key and cannot wait for Bob to provide a commitment:

Bob has the (private, public) EC key pair $(b, B=bG)$, where $G$ is a well-known base point.

Alice picks a uniformly random 128-bit integer $s$, and informs Bob of $s$.

Bob calculates $X=bH_p(s)$, where $H_p()$ means to hash the input and interpret the result as an EC point. This means that the private key $x$ such that $X=xG$ is unknowable.

Bob calculates $t=H_4(X \mathbin\| i)$, where $i$ is a 128-bit number initially set to the value zero and $H_4()$ means to truncate the result of a cryptographically secure hash to 4 bits. He then uses rejection sampling to determine his lottery ticket $v$ as follows:

If $0\leq t\leq 9$, Bob determines $v=t+1$. Otherwise, he increments $i$ and tries again. Bob must accept the first value of $t$ that is in the required range, and Alice will be able to check he has done so.

When Bob is ready to announce his lottery ticket $v$, he needs to announce $X$ and provide a discrete-log-equivalence proof demonstrating that the point $X$ on the base point $H_p(s)$ shares the same private key $b$ as Bob's public key $B$ on the base point $G$. This proves that $X$ was calculated correctly.

The construction $X=bH_p(s)$ is known as a verifiable pseudo-random function (VPRF). It allows Alice to choose the input of a PRF that only Bob will be able to perform, and for which Bob will be able to provide proof that he has performed the PRF correctly.

Note that Bob must check that Alice has not provided the same seed $s$ twice, as this would allow Alice to cause Bob to receive the same lottery ticket value again in the future.





Comments (3)

  • +1 – A small comment. Can't we get rid of this extra proof by using pairing friendly curves? — Aug 11, 2022 at 18:31  
  • +1 – @ManishAdhikari I don't currently have enough expertise with pairings to comment. If you can describe how you'd do that, I'd be very interested if you posted your technique as an answer. The DLEQ proof is fairly simple. — Aug 11, 2022 at 18:39  
  • +0 – Nothing much. I am not talking about a new technique. But with pairing friendly curves X can itself act as a proof for VPRF $f_b(s)=H_4(X || i)$ for first i that gets the value in the range. Just check that $e(X,G)=e(H_p(s),B)$ — Aug 11, 2022 at 18:42