秘密共享

目的

为了防止单个用户权限过大，导致系统崩溃或被攻击，可以将一个秘密分割成多个部分，分发给不同的用户，只有当足够数量的用户合作时，才能恢复出原始秘密。

分类

1. $(t,n)$ 门限：将秘密分成 $n$ 份，至少 $t$ 份才能恢复出秘密，$t \leq n$。
2. $(n,n)$ 门限：将秘密分成 $n$ 份，所有 $n$ 份才能恢复出秘密。

构造门限的方式

2-N

构造直线 $y = ax + b$，只需其中两点即可确定一条直线。

3-N

构造二次曲线 $y = ax^2 + bx + c$，只需其中三点即可确定一条二次曲线。

t-N

构造 $t-1$ 次多项式 $y = a_{t-1}x^{t-1} + a_{t-2}x^{t-2} + \cdots + a_1x + a_0$，只需其中 $t$ 点即可通过使用拉格朗日插值确定一条 $t-1$ 次多项式。

只有这部分的秘密共享方案叫做Shamir秘密共享方案。

存在问题

1. 存在对于参与者的抗欺诈性问题，既参与者可能会提供错误的份额，导致无法恢复出正确的秘密。
2. 不能防止分发者的欺诈性问题，既分发者可能会分发错误的份额，导致无法恢复出正确的秘密。

VSS方案

这里介绍Feldman的公开验证秘密共享方案（Verifiable Secret Sharing, VSS），该方案可以解决上述问题。

参数设定

• 选取大素数 $p$ 与生成元 $g \in \mathbb{F}_p^*$，并满足离散对数难题假设。
• 阈值参数 $t$、参与者数量 $n$ 与 Shamir 门限方案一致。

承诺阶段

分发者随机选择 $f(x) = a_0 + a_1 x + \cdots + a_{t-1} x^{t-1}$，其中 $a_0$ 为秘密。
计算并广播承诺 $C_j = g^{a_j} \; mod \; p$（$0 \le j < t$），同时给每个参与者 $P_i$ 私下发送份额 $s_i = f(i)$。

验证阶段

参与者 $P_i$ 接收份额后，公开验证条件

$g^{s_i} == \prod_{j=0}^{t-1} C_j^{i^j} \; mod \; p$

若等式成立，则确认分发者诚实；若不成立，参与者可拒绝该份额。

恢复阶段

任意 $t$ 个参与者可通过 Shamir 插值恢复 $f(0)=a_0$。由于承诺已固定多项式系数，分发者无法再事后篡改秘密，同样参与者若提交伪造份额也会在验证中被识别。