16
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ Sealing or encryption is not the right tool for the job here, as it explicitly converts a plaintext message to ciphertext. If Alice has plaintext then your game is over before it started. The trick would be to derive some secret using information solely from Alice, while not allowing for trying random numbers - something like ephemeral-static key agreement possibly? You might also need a notary / third party of some kind. $\endgroup$
    – Maarten Bodewes
    Aug 11 at 7:48
  • $\begingroup$ Does Alice need to be able to send different (unknown) messages to different people? I suppose that's an important property of selling numbered lottery tickets. $\endgroup$ Aug 13 at 22:52
  • $\begingroup$ @PaŭloEbermann Yes, only Bob should be able to "scratch off" and observe the ticket addressed to him (not even Alice should be able to), and in principle Alice should be able to generate and send different tickets (containing possibly-different random numbers) to Bob again, or to others. $\endgroup$
    – mherzl
    Aug 14 at 4:48
  • 1
    $\begingroup$ 'is there a way that Alice can prepare and send the "ticket" to Bob using only one message' <- With my method, the only thing Alice has to do is send one 128-bit message $s$. Not only that, but she can broadcast the same $s$ to everyone, and only those whose public keys are allowed to participate will be able to derive their ticket and make a claim. This relies on Alice knowing in advance which public keys are eligible for the lottery, to prevent people from generating millions of key pairs until they find one that will win the lottery, and then declaring that key pair as their identity. $\endgroup$
    – knaccc
    Aug 14 at 13:55
  • $\begingroup$ Awesome, thank you @knaccc! $\endgroup$
    – mherzl
    Aug 14 at 15:48

4 Answers 4

21
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ A small comment. Can't we get rid of this extra proof by using pairing friendly curves? $\endgroup$ Aug 11 at 18:31
  • 1
    $\begingroup$ @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. $\endgroup$
    – knaccc
    Aug 11 at 18:39
  • $\begingroup$ 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)$ $\endgroup$ Aug 11 at 18:42
7
$\begingroup$

The primitive you are looking for is called a (two-party) coin-flipping protocol: an interactive, two-party protocol which allows two players to sample a random number without being able to bias the outcome.

The other answers have described some classical examples of coin-flipping protocols over a ring $\mathbb{Z}_n$: each party picks a random number from the prescribed set and commits to it; then, both parties open the commitment, and the sum of the numbers over $\mathbb{Z}_n$ is the result.

An important point of caution, though: the above protocol is fine if you apply it in a context where the protocol will be ran only once and there is no point in aborting (terminating early) the protocol. The point is the following: often, when we define a coin-flipping protocol, we can envision using it in many different runs of larger protocols. But with the above protocol, one of the party can see the outcome before the other party, and decide to terminate the protocol if he is not happy with the result.

Think of it as follow: we run many protocols online which start with a coin-flipping. Everytime, Bob sees the result first, and Bob gains an advantage if the outcome is odd. Then Bob could simply decide to abort the protocol whenever the outcome is even (claiming, e.g., a network failure). This would effectively bias the outcome of the protocol, when we condition on successful termination, and provide Bob an unfair advantage in any successful execution.

There is an important area of cryptography that deals precisely with this problem, which is called fair coin flipping. The short version is:

  • It is provably impossible to remove all bias - one of the parties will always be able to gain some advantage by terminating early
  • You can do much better than the above protocol, though, and reduce the bias to $O(1/\sqrt{r})$ (assuming one-way functions) or even $1/r$ (assuming public-key cryptography) using a protocol with $r$-rounds.
  • There are some converse results as well (showing these assumptions are necessary)
  • You can do better in the quantum setting (this result is provably optimal)
  • You can partially circumvent this issue by using timed commitments or other related notions.
$\endgroup$
1
$\begingroup$
  1. Bob generates a random number, hashes it with a cryptographically secure algorithm, and gives the hash to Alice
  2. Alice also generates a random number and sends her number to Bob
  3. Bob takes his number and XORs it with Alice's number. The resulting number is the lottery ticket. Because neither party knows what number the other party generated, neither party could have predicted the result.
  4. Bob sends his random number to Alice. Now Alice can verify Bob's hash to confirm that he did not change his number after receiving the number from Alice. The ticket is now known to both parties.
$\endgroup$
1
  • 1
    $\begingroup$ This is almost exactly the same as the protocol described in the first part of knaccc's answer, except that your version doesn't ensure that the output is a number between 1 and 10 as specified by the OP (bitwise XOR is not closed on that set) and is missing some details needed to make the commitment scheme secure (e.g. Bob needs to either choose his number from a large enough set to prevent Alice from guessing it by brute force, or blind it by appending an additional large random number to the hash input). $\endgroup$ Aug 13 at 12:38
0
$\begingroup$

Encrypted data and signatures should be virtually indistinguishable from random bits. If they are not, then there is likely a vulnerability in the algorithm. So I'm ignoring that and assuming an algorithm that generates signatures that are for all intents and purposes random bits that can't be associated with the incoming data without knowing the key.

  1. Alice provides Bob some random data and a set of rules
  2. Bob signs the random data with his public key and applies the rules to the signature to get the number. At this point, Bob is the only person that knows what the signature looks like and therefore what the number is.
  3. Later Bob can provide the signature to Alice, and Alice can use Bob's public key to verify the signature was applied to the exact data that Alice provided, and use the rules she provided to calculate the number.

Any power of 2, such as 1-8 or 1-16, is uniformly possible. Let's say a signature is 1024 bits. Alice may provide the rules 'Look bits 57-60 for a 4 bit number from 0-15'.

1-10 is not exactly possible, but can be closely approximated. The rules could be that Bob should treat the entire signature as a 1024 bit unsigned integer and take the value mod 10 to get 0-9. Some digits will be very slightly more likely than others, but the difference is so small that you can ignore it for practical purposes. The decimal numbers 0-6 would occur 1797693134862315907729305190789024733617976978942358629823994724593847971630483535632962422413721 times and the numbers 7-9 would only occur one fewer times.

$\endgroup$
19
  • $\begingroup$ I don't think there's any need for signatures. If Bob generates a random sequence of bits B and publishes a hash H(B), and if Alice upon receiving and authenticating the hash (whether via digital signatures, or having received it via secure medium such as personal delivery) sends Bob a random string A, then Bob will be able to compute H(A+B) faster than anyone who has not had time to compute B from H(B)--an action which, if H is a good hash function, should be infeasible on any human time scale. $\endgroup$
    – supercat
    Aug 11 at 21:07
  • 1
    $\begingroup$ @supercat I'm a little lost with your explanation. Where is the random number from 1-10 in your example? In the bits of H(A+B)? So first Bob must provide H(B) to Alice, then Alice provides A to Bob, then Bob calculates H(A+B) and derives a number from 1-10 from the result according to some rules as in my answer, then Bob provides B and H(A+B) to Alice to verify that H(B) matches the hash she was given earlier and that H(A+B) gives a new hash corresponding to the number that Bob got? $\endgroup$ Aug 11 at 21:29
  • 1
    $\begingroup$ Given a method of producing a large blob of bits which are effectively chosen uniformly from a random set, producing a number 1-10 is trivial as you note. Otherwise, you seem to understand what I'm describing perfectly. The key point is that there's no need for Alice to have any secret other than her random string of bits, which has no semantic significance beyond being a random string of bits. $\endgroup$
    – supercat
    Aug 11 at 21:47
  • 3
    $\begingroup$ Some signature algorithms are designed in such a way that signing the same material multiple times will always yield a bit-identical signature, but that feature is not universal. The 256-bit elliptical curve signature algorithm for example, takes as input 256 bits of data to be signed and 256 bits of nonce that be different for every signature and which, if revealed to anyone, would allow the key to be determined, and would produce 512 bits of output. While there is a deterministic form of the algorithm, it would be impossible for anyone to distinguish a deterministic-nonce signature... $\endgroup$
    – supercat
    Aug 11 at 22:23
  • 1
    $\begingroup$ ...from a random-nonce signature without having the private key or information sufficient to compute it. If Bob were to generate random-nonce signatures until he found a nonce where Alice's rules would yield the desired result, there would be no way for anyone without the key to distinguish that from a deterministic-nonce signature. $\endgroup$
    – supercat
    Aug 11 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.