Verifiable Secret Sharing

参考文献：

1. Feldman P. A practical scheme for non-interactive verifiable secret sharing[C]//28th Annual Symposium on Foundations of Computer Science (sfcs 1987). IEEE, 1987: 427-438.
2. Shamir Secret Sharing：https://blog.csdn.net/weixin_44885334/article/details/124640944

Verifiable Secret Sharing

$(n,t,u)-$秘密共享方案：一共$n$个参与方，任意的$n^{\prime }\le t$个参与者无法恢复秘密，任意的$n^{\prime }\ge u$个诚实参与者可以正确恢复秘密。

但是，原始的 SS 协议（比如 Shamir SS）在恢复秘密时，如果恶意参与者发送了错误的share，那么诚实参与者将几乎不会计算出正确的秘密。因为他们无法区分出正确的shares。

如果让秘密的分发者（记做 dealer）在share上签名，那么是否可以解决问题？不能。因为 dealer 也是 SS 协议的参与者，如果他被入侵了，那么就可以伪造出错误的share，让其他诚实参与者无法恢复出正确的秘密。

我们额外要求：

1. 在 Share 阶段，参与者可以验证 dealer 通过隐私信道发放的 shares 是否有效。
2. 在 Recover 阶段，参与者可以 check 其他参与者通过广播信道揭露的 shares 的正确性。

另外，交互式VSS协议的通信量过大，不适用于某些信道，并且无法并行。非交互式VSS：在 Share 阶段，只有一个处理器（叫做leader）发送消息，可以执行数轮通信。

VSS定义

$(n,t,u)-$非交互式可验证秘密共享协议，是一组概率多项式时间的算法$(Share,Recover,Check,Encrypt)$：

1. $Encrypt$是加法同态的加密方案，令$Y\leftarrow Encrypt(\alpha )$，其中$\alpha$是秘密

2. $(Share,Recover)$是一个$(n,t,u)-$秘密共享方案

   1. $({\alpha }_1,\cdots ,{\alpha }_n)\leftarrow Share(\alpha )$
   2. $\alpha \leftarrow Recover({\alpha }_{i_1},\cdots ,{\alpha }_{i_u}{)}_{I\subseteq [n]}$

3. $Check$是利用密文同态性质的校验算法，任意的参与者$j$都可以检验
   $$Check(Y,j,{\alpha }_j)=1⟺Y=Encrypt(\alpha )\wedge (\cdots ,{\alpha }_j,\cdots )=Share(\alpha )$$

注意，$Share$中隐含着$Encrypt$的调用，$Y$是每个${\alpha }_j$的一部分。

Feldman（1987）

Feldman 基于 Shamir 方案，添加了基于离散对数的同态加法加密算法，给出了第一个非交互式的 VSS 方案。

原始论文为了用模拟器证明安全性，对方案的描述十分复杂。下面结合其他介绍VSS的文章，给出更简洁的描述。

Share 阶段：

1. 选定素域乘法群或者椭圆曲线加法群$G$，其上的离散对数问题是困难的（注意，剩余类加法群的离散对数问题是简单的）。令$g$是生成元。

2. dealer $i$ 拥有秘密$\alpha$，利用 Shamir 方案随机选择$t$次（注意不同表述里的$t$是否取等）多项式
   $$f(x)=a_0+\sum _{i=1}^t{a}_i{x}^i$$
   其中常数项为$a_0=\alpha$

3. dealer 对它的$t+1$个系数加密，使用的加密算法为
   $$g^a\leftarrow Encrypt(a)$$

   它是明文加法群和密文乘法群之间的群同态，单向性基于离散对数问题。

   计算多项式系数的密文（可以叫做承诺，commitment），
   $$c_0=g^{a_0},c_1=g^{a_1},\cdots ,c_t=g^{a_t}$$

   通过广播信道发送给所有参与者。

4. dealer 利用 Shamir 方案，生成 shares，
   $$\{(x_1,f(x_1)),\cdots ,(x_n,f(x_n))\}\leftarrow Share(\alpha )$$

   然后通过隐私信道，将${\alpha }_j:=(x_j,f(x_j))$发送给参与者$j$

5. 每个参与者都可以检验自己的 share 的有效性，
   $$c_0\cdot c_1^{x_j}\cdot c_2^{x_j^2}\cdot \cdots \cdot c_t^{x_j^t}==Encrypt(f(x_j))$$

Recover 阶段：

1. 足够多的参与者通过广播信道披露自己的 shares，$(x_j,f(x_j))$

2. 每个参与者都自行验证这些 shares 的有效性，
   $$c_0\cdot c_1^{x_j}\cdot c_2^{x_j^2}\cdot \cdots \cdot c_t^{x_j^t}==Encrypt(f(x_j))$$

3. 每个参与者选出至少$t+1$个有效的 shares，利用 Shamir 方案的拉普拉斯插值算法，恢复出秘密$\alpha$

易知，只要$t+u\le n$那么就可以 Recover 秘密，Shamir 协议中$u=t+1$。因此，Feldman 协议可以抵挡至多$(n-1)/2$个恶意敌手的攻击。通信复杂度为$O(nk)$，计算复杂度为$O((n\log n+k)\cdot nk\log k)$，其中$k$是安全参数。

另外，对于通信信道的假设也可以弱化：

1. 隐私信道：点对点隐私信道的花费很大。如果事先进行密钥交换，那么任意一个完整网络（complete network，任意两点之间有通路即可）就够了，发送给$j$的 share 被加密。
2. 广播信道：广播信道这个假设过强。利用十字军协议（拜占庭协议的弱化版），那么也不再需要广播信道，不过此时只有$t<n/3$。如果使用签名消息，那么可以再提升回$t<n/2$。

非交互 VSS 的用途

1. 在任意完整网络上，搭建起同步广播信道：第$r$轮消息被 Share 给每个人后，再一起 Recover 同时得到这个消息。
2. 每个参与者都可以并行地充当 dealer，并行地分发秘密。
3. 已经证明，在非广播信道上运行非交互 VSS，可以实现快速的常数时间拜占庭协议。