多方秘密生成协议

Question

其目的是在可信服务器上创建一个秘密S，让用户A、B和C分别向服务器发送一个私有种子，这样任何两个用户都可以通过重新提交相应的种子来恢复S。

编辑:实际用例是创建一个秘密，服务器可以在内存中使用，但不会在磁盘上持久化。如果内存被重置，任何两个用户都可以协作在服务器内存中重新创建相同的秘密(可能需要一些持久恢复参数的帮助，而这些参数本身无法重新创建该秘密)。

它看起来像是Shamir秘密共享方案的“反向”版本，在该方案中，所有用户都从他们选择的共享开始，该算法需要将这些共享压缩成满足阈值恢复标准的秘密。

实现这种协议的最简单方法是什么？

Answer 1

您可以执行以下操作：

1. 服务器生成一个线性方程$y=ax+s$，其中$a$是从有限域随机选择的，$F_p$和$s\in F_p$是秘密。
2. 对于来自$A、B、C$的值，让我们将它们称为$x_A、x_B、x_C$。在这些$x$值处计算线性方程，服务器得到$y_A、y_B、y_C$。
3. 服务器分别将$y_A、y_B、y_C$返回给$A、B、C$。

现在，每一方都有一份股票，即$(x_i，y_i)$。任何两种股票都可以重建秘密$s$。

这本质上是(2,3)-Shamir秘密共享。

Answer 2

我想通了。给定三个种子$A$、$B$和$C$，我们需要计算内存中的$S$，并存储恢复参数$\alpha$和$\beta$，以便方程$$ x^3 +αx^2 +βx=S $$有三个根：$(A+B)$、$(B+C)$和$(A+C)$。

因此，在三个用户将所选种子发送到服务器后，服务器计算$$ \alpha = -2(A+B+C) $$ $$ \β= A^2 + B^2 + C^2 + 3(AB + AC + BC) $$ $$ S= AB^2 + AC^2 + BA^2 + BC^2 + CA^2 + CB^2 + 2ABC $$，并只存储恢复参数$\alpha$和$\beta$。稍后，三个用户中的任何两个都可以将种子发送回服务器(让它们是$S_1$和$S_2$)，并且相同的秘密将被重新计算如下：$$ S= (S_1+S_2)^3 +alpha(S_1+S_2)^2+\β(S_1+S_2) $$