秘密共享

目的

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

分类

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

构造门限的方式

2-N

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

3-N

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

t-N

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

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

存在问题

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

VSS方案

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

参数设定

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

承诺阶段

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

验证阶段

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

$$g^{s_i}==\prod _{j=0}^{t-1}{C}_j^{i^j}modp$$

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

恢复阶段

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