Deciding Movie-Night Order (Passive Security)

Every Wednesday some friends and I have a movie-night for which one person always chooses the movie (read as: forces the others to watch). For reasons unknown to me, we don’t do it in Round-Robin style but choose the ordering randomly after everyone has had their turn.

Since the great pandemic of 2019, the movie night had to be done online - however, this meant that we ran into the problem of determining a fair, totally random order. If someone chooses an ordering using random.org the others cannot be sure that they did not cheat. Even with sharing their computer screen, we would not know. Maybe it’s just an elaborate screen recording… Maybe they changed the HTML… Maybe they are running a MITM attack on their network to intercept and change the HTTP responses… Maybe they got an internship at random.org and managed to bias their randomness generators… who knows…

For important applications such as choosing the movie-night order, we need proper information-theoretic assurances. (In the past we abused hash functions to construct commitment schemes)

Therefore, to determine the order fairly, we will construct a passively secure protocol to choose a random value:

There are 5 parties: $P_1=DP, P_2=WD, P_3=ToB, P_4=TB, P_5=FO$

Every party chooses a random value $s_P \in GF(120)$ and creates a random polynomial of degree at most $4$ in $GF(120)$ such that their secret input $s_P$ is at position 0:

$f_{P}(0) = s_P$

$f_{P}(x) = s_P + c_1 \cdot x + c_2 \cdot x^2 + c_3 \cdot x^3 + c_4 \cdot x^4$

Now we do a Shamir Secret Sharing Every party evaluates their polynomial $f(x)$ at positions $x \in {1, 2, 3, 4, 5}$ and sends the evaluation to the corresponding party.

$f_{P}(1) \rightarrow DP$

$f_{P}(2) \rightarrow WD$

$f_{P}(3) \rightarrow ToB$

$f_{P}(4) \rightarrow TB$

$f_{P}(5) \rightarrow FO$

We want to calculate the polynomial $f(x) = \Sigma_{i \in P} f_i(x)$ and use $f(0)$ as our random number which determines the order according to the table below.

Since Shamir Secret Sharing is linear in addition, everybody can add up their shares such that we obtain a sharing of the $f(x)$ polynomial.

Now we reconstruct $f(x)$ towards each party and everybody broadcasts their value.

For the reconstruction, everyone broadcasts their value and we interpolate the polynomial with Lagrange Interpolation (we omit the uniqueness proof): We have n points ${ (\alpha_1, s_1), (\alpha_2, s_2), …, (\alpha_n, s_n) }$ on some polynomial and we want to calculate this polynomial. We can certainly write it as:

$f(x) = s + \lambda_1(x)\cdot x^1 + \lambda_2(x)\cdot x^2 + … + \lambda_t(x)\cdot x^t$

where

• $\lambda_i(x) = 0$ $\text{ if } i \neq x \land x \in {s_j}$
• $\lambda_i(x) = 1$ $\text{ if } i = x$
• $\lambda_i(x) = \text{anything}$ else

if we can write the $\lambda_i$-Functions as a polynomial, then $f(x)$ would certainly also be a polynomial.

Let’s construct the $\lambda_i$ function:

$\lambda_i(x) = \Pi_{j=1,j\neq i}^n \frac{x-a_j}{a_i-a_j}$

We can easily see that this function has all the properties we want for $\lambda_i$.

Therefore, we can construct the whole polynomial based on our points as:

$g(x) = \Sigma_{i=1}^{n} \lambda_i(x)\cdot s_i$

or for our case with $n=5$:

$g(x) = \lambda_1(x)\cdot s_1 + \lambda_2(x)\cdot s_2 + \lambda_3(x)\cdot s_3 + \lambda_4(x)\cdot s_4 + \lambda_5(x)\cdot s_5$

$=\frac{x-2}{1-2} \cdot \frac{x-3}{1-3} \cdot \frac{x-4}{1-4} \cdot \frac{x-5}{1-5} \cdot s_1 +\frac{x-1}{2-1} \cdot \frac{x-3}{2-3} \cdot \frac{x-4}{2-4} \cdot \frac{x-5}{2-5} \cdot s_2 +\frac{x-1}{3-1} \cdot \frac{x-2}{3-2} \cdot \frac{x-4}{3-4} \cdot \frac{x-5}{3-5} \cdot s_3 +\frac{x-1}{4-1} \cdot \frac{x-2}{4-2} \cdot \frac{x-3}{4-3} \cdot \frac{x-5}{4-5} \cdot s_4 +\frac{x-1}{5-1} \cdot \frac{x-2}{5-2} \cdot \frac{x-3}{5-3} \cdot \frac{x-4}{5-4} \cdot s_5$

We calculate the result value as $g(x=0)$.

Everybody now broadcasts their result value. If a party sees a value that is inconsistent, it broadcasts a complaint, and we restart the protocol. (This opens up the possibility that somebody claims that their value is inconsistent if they just don’t like the outcome. They can then DOS the protocol. We could remedy this by adding an information-theoretically secure distributed commitment scheme but that would be “too over-engineered” )

If a party sees consistent values from everyone, then they broadcast acceptance and we accept the value $f(0)$ as our random value that determines the ordering.

Next, we need security against active adversaries, ensure termination and make the protocol secure against replay and impersonation attacks.

However, I fear that, if I do this, then I won’t have any friends left to watch movies with… (although that would also solve the problem…)