Multiparty secret generation protocol

Question

The goal is to create a secret S on a trusted server by having users A, B and C each send a private seed to the server, in such a way that any 2 of them can later recover S by resubmitting their corresponding seeds.

Edit: the actual use case is to create a secret that the server can use in memory but won't persist on the disk. If the memory is reset, any two users can collaboratively recreate the same secret in the server's memory (with the possible help of some persistent recovery parameters that cannot, on their own, recreate the secret).

It looks like a "reversed" version of the Shamir Secret Sharing Scheme, where all users start with their chosen share and the algorithm needs to crunch those shares into a secret that meets the threshold recovery criteria.

What is the simplest way to implement such a protocol?

Answer 1

You can do the following:

1. The server generates a linear equation $y=ax+s$ where $a$ is chosen randomly from a finite field $F_p$ and $s\in F_p$ is the secret.
2. For the values from $A,B,C$, let’s call them $x_A,x_B,x_C$. Evaluate the linear equation at these $x$ values and the server gets $y_A,y_B,y_C$.
3. The server returns $y_A, y_B,y_C$ to $A,B,C$ respectively.

Each party now has a share which is a pair $(x_i,y_i)$. Any two shares can reconstruct the secret $s$.

This is essentially (2,3)-Shamir secret sharing.

Answer 2

I figured it out. Given the three seeds $A$, $B$ and $C$, we'll need to compute $S$ in-memory and store the recovery parameters $\alpha$ and $\beta$ such that the equation $$ x^3 + \alpha x^2 + \beta x = S $$ has exactly three roots: $(A+B)$, $(B+C)$ and $(A+C)$.

So after the three users send over their chosen seeds to the server, the server computes $$ \alpha = -2(A+B+C) $$ $$ \beta = A^2 + B^2 + C^2 + 3(AB + AC + BC) $$ $$ S = AB^2 + AC^2 + BA^2 + BC^2 + CA^2 + CB^2 + 2ABC $$ and stores only the recovery parameters $\alpha$ and $\beta$. At a later time, any two of the three users can send their seeds back to the server (let these be $S_1$ and $S_2$) and the same secret will be recomputed again as follows: $$ S = (S_1+S_2)^3 + \alpha(S_1+S_2)^2 + \beta(S_1+S_2) $$