2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ideally the users won't need to store any additional information, but I believe your solution can be easily adapted to persist the y parameters on the server, along with a. I'm not sure in this case if the server admin (presumably knowing a and the three y values) colluding with a user (who knows one of the corresponding x values) will be able to recover the secret. $\endgroup$ – Lucian Boca Jun 30 '18 at 21:32
  • $\begingroup$ The server is trusted means that it is allowed to know everything. The secret is generated by the server so an admin with full control over the server can get the secret without colluding with any user. BTW if you are worried about collusion, you also need to revise your solution below because given $\alpha$ and one user’s value, $S$ Can be recovered. For example, given $\alpha$ and $A$, one can recover $B+C=-\alpha/2-A$, then use that to get $S$. $\endgroup$ – Changyu Dong Jun 30 '18 at 21:57
  • $\begingroup$ I haven't been able to express $S$ only in terms of $\alpha$, $\beta$ and $A$. How would that work? $\endgroup$ – Lucian Boca Jun 30 '18 at 22:03
  • 1
    $\begingroup$ You can get B+C from $\alpha$ and A as showed above. Then you can get S by your last formula by substituting $S_1+S_2$ with B+C. $\endgroup$ – Changyu Dong Jul 1 '18 at 6:20
1
$\begingroup$

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) $$

$\endgroup$

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.