对于 2 / 3

keygen

各方构造随机多项式：

$p_1(x) = 1 + 2x$

$p_2(x) = 2 + 3x$

$p_3(x) = 3 + x$

各方算出 $p_i(j)$：

$p_1(1)=3, \space p_1(2)=5, \space p_1(3) = 7$

$p_2(1)=5,\space p_2(2)=8, \space p_2(3) = 11$

$p_3(1)=4, \space p_3(2)=5, \space p_3(3) = 6$

各方算出私钥分片：

$x_1 = 3 + 5 + 4 = 12$

$x_2 = 5 + 8 + 5 = 18$

$x_3 = 7 + 11 + 6 = 24$

共享私钥为每个多项式的常数项之和：$x = 1 + 2 + 3 = 6$

共享私钥和私钥分片之间满足拉格朗日插值：

$$ \begin{align} 6 &= \frac{x-2}{1-2}\frac{x-3}{1-3} \cdot 12 + \frac{x-1}{2-1} \frac{x-3}{2-3} \cdot 18 + \frac{x-1}{3-1}\frac{x-2}{3-2} \cdot 24 \\ &= \frac{0-2}{1-2}\frac{0-3}{1-3} \cdot 12 + \frac{0-1}{2-1} \frac{0-3}{2-3} \cdot 18 + \frac{0-1}{3-1}\frac{0-2}{3-2} \cdot 24 \\ &= 3 \times 12 - 3 \times 18 + 1 \times 24 \end{align} $$

推第三方私钥分片

已知 $x_1 = 12, \space x_2 = 18$，可以推出共享私钥为

$$ \begin{align} 6 &= \frac{x-2}{1-2} \cdot 12 + \frac{x-1}{2-1} \cdot 18 \\ &= \frac{0-2}{1-2} \cdot 12 + \frac{0-1}{2-1} \cdot 18 \\ &= 2 \times 12 - 1 \times 18 \\ \end{align} $$

又因为共享私钥和私钥分片之间满足拉格朗日插值

$$ \begin{align} 6 &= \frac{x-2}{1-2}\frac{x-3}{1-3} \cdot 12 + \frac{x-1}{2-1} \frac{x-3}{2-3} \cdot 18 + \frac{x-1}{3-1}\frac{x-2}{3-2} \cdot 24 \\ &= \frac{0-2}{1-2}\frac{0-3}{1-3} \cdot 12 + \frac{0-1}{2-1} \frac{0-3}{2-3} \cdot 18 + \frac{0-1}{3-1}\frac{0-2}{3-2} \cdot x_3 \\ &= 3 \times 12 - 3 \times 18 + 1 \times x_3 \end{align} $$

所以可以解出 $x_3 = 24$