How do I pick a shared random number?

Question

Let's suppose I have three friends, all remote. We want to randomly and fairly pick one person to be the first player in a game. In order to do so, we'll each be assigned a unique number in {1, 2, 3, 4} and then roll a fair four-sided die (1d4). This works in person because we can all verify that the correct die was rolled only once, but not remotely. Suppose I am the one to roll the die - the others all have to trust that I'm not lying. Or perhaps I record a video of me rolling the die. This still doesn't work because I could simply have rolled until I got the result I wanted, then use that video.

One way I thought of doing this was to have a service that would generate a number. Each person would verify to the service that they would accept the result, then after all of us have done so, the service will generate a random number for us. Then we could retrieve the random number, which would be the same for us all. The issues with this is that we must trust the third-party service.

Is there a simple, trustless way to generate small random numbers by hand (with dice)? Such that even if some subset of people are malicious, they can't affect the outcome in a meaningful way? I suppose we can rule out collusion, or perhaps limit collusion to m of n people (i.e., 2 of 4 people can collude without affecting the outcome but not more than that).

I'm specifically looking for solutions that will work with "small" numbers - numbers found on standard dice. Less than 20 would be ideal, but if the only viable solution needs a d100 that would probably work.

Answer 1

I believe the problem can be solved with MPC (multi-party computation) techniques. Here is a protocol that I think works when the majority of people are honest (i.e., at most $\left\lfloor\frac{n-1}2\right\rfloor$ collusions out of $n$ people). I haven't got time to verify for now. Maybe I will update this answer to prove its security later.

Protocol

1. Each person $i$ generates two secret numbers from $\mathbb Z_m$ (suppose we want $m$ possible outcomes). One is used as the seed ($s_i$), and the other is used as the mask ($m_i$).
2. Each person $i$ sends out one message with the initial value $s_i+m_i$ and passes it to the next person.
3. On receiving one message:
   1. If the message is sent from herself, Person $i$ extracts the value and subtracts it by $m_i$. Denote her final value by $v_i$.
   2. If not, Person $i$ adds the value by $s_i$ and passes the message to the next person.
4. Person $i$ compares her $v_i$ with everyone else's $v_j$. If they are all the same, Person $i$ votes that Person $v_i$ is the first player.
5. If Person $v_i$ receives votes from all the people, she is the first player.

Analysis (NOT formal proof)

Ideally, each person's $v_i$ should equal to $\sum_{i=1}^ns_i$. Hence, they can reach a consensus if each person obeys the protocol. Since each honest person has a say in the final result, $v_i$ should be uniformly random. Next, we consider subversive people.

Since the majority of people are honest, there must exist two honest people who are adjacent. Let's say they are $i$ and $i+1$. Regardless of how others behave (e.g., whether they are benign or malicious), the two people can keep their local seeds and masks secret (even if other people exchange information). The reason is that messages are handed to People $(i+1)$ by People $i$. Even if other people intercept messages before People $i$ and after People $(i+1)$, they can only compute the sum $s_i+s_{i+1}$ and cannot infer $s_i$ or $s_{i+1}$ alone. Moreover, they cannot tell $s_i$ nor $m_i$ from the initial value.

Additional Notes

1. The order of message passing is important: Each message should be passed in a circular manner (although a minority of people may disobey the rule). Such an order can be established by leader election. After the election, the leader delegates her leadership to a second person and then a third person, and so on, until every person has a fixed position in the circle.

2. Once the beginner is agreed, she is purely randomly chosen. It does not mean that each run of the protocol will result in a consensus. In fact, the protocol may indefinitely fail to reach a consensus if some people continue to undermine it.

Answer 2

One method is to have everyone simultaneously generate their own random number - for example, everyone rolls a 4-sided die - and you take the sum of all the random numbers modulo 4 (or equivalently you count down the list equal to the sum, looping back to the start each time). Then as long as no-one has perfect information of what everyone else's numbers will be ahead of time, even if they cheat they can't really affect the outcome. It's also robust to collusion, because if $n-1$ people decide on their combined result the final outcome is still completely decided by the remaining person.