verifiable secret sharing可验证的秘密共享

1. secret sharing秘密共享 1.1 secret sharing definition

在Adi Shamir 1979年论文《How to share a secret》（发表在论文《Safeguarding cryptographic keys 》之后，实现方式不同且效率更低。），举了个例子，若11个人需要6个以上到场才能打开某个带锁的箱子，则至少需要462把锁，每个人至少需要到252把钥匙。（具体解法可参见博客锁和钥匙的分配问题。）

假设需要共享的秘密为某数据 D D D，将 D D D切分为 n n n段 D 1 , . . . , D n D_1,...,D_n D1​,...,Dn​，需要实现的是：

• 1）知道大于等于 k k k段 D i D_i Di​信息，则可以恢复出完整的数据 D D D；
• 2）知道少于等于 k − 1 k-1 k−1段 D i D_i Di​信息，则无法确定完整的数据 D D D。

( k , n ) (k,n) (k,n)称为阈值机制。

有效的阈值机制在管理密码学key时非常有用。通常，为了保护数据，我们可以对数据进行加密，但是为了保护加密用的key，需要有专门的密钥key保护措施： 通过使用 ( k , n ) ， n = 2 k − 1 (k,n)，n=2k-1 (k,n)，n=2k−1阈值机制，将密钥key分为 n n n份分别保存，可以在 k − 1 k-1 k−1块密钥段损坏的情况下，仍能恢复密钥key；而在非法获得哪怕 k − 1 k-1 k−1块正确的密钥段也无法重构出正确的密钥key。

( k , n ) (k,n) (k,n)阈值机制特别适于一群相互怀疑但又不得不合作的群体使用。

1.2 a simple ( k , n ) (k,n) (k,n) threshold scheme

基于的多项式插值：当有 k k k个不同的点 ( x 1 , y 1 ) , . . . , ( x k , y k ) (x_1,y_1),...,(x_k,y_k) (x1​,y1​),...,(xk​,yk​)时，任意两个 x i x_i xi​均不相同，可唯一确定 k − 1 k-1 k−1阶的多项式 q ( x ) q(x) q(x)，使得对于任意的 i i i，均满足 q ( x i ) = y i q(x_i)=y_i q(xi​)=yi​。

将其推广到 ( k , n ) (k,n) (k,n) threshold scheme可为： 将数据 D D D表示为number数字，切分为数据段 D i D_i Di​，取任意的 k − 1 k-1 k−1阶多项式 q ( x ) = a 0 + a 1 x + . . . + a k − 1 x k − 1 q(x)=a_0+a_1x+...+a_{k-1}x^{k-1} q(x)=a0​+a1​x+...+ak−1​xk−1，其中 a 0 = D a_0=D a0​=D，对 n n n段信息都进行计算，有： D 1 = q ( 1 ) , . . . , D i = q ( i ) , . . . , D n = q ( n ) D_1=q(1),...,D_i=q(i),...,D_n=q(n) D1​=q(1),...,Di​=q(i),...,Dn​=q(n) 所以，对于任意k个数据段子集（及相应的索引 i i i），可通过多项式插值的方式计算多项式 q ( x ) q(x) q(x)的系数，然后可计算出完整的 D D D值， D = q ( 0 ) D=q(0) D=q(0)。若仅知道 k − 1 k-1 k−1个数据段，则无法计算相应的 D D D值。

为了使计算结果更准确，将采用模运算来替代实数域运算。可以取比 p > D , p > n p>D,p>n p>D,p>n的素数 p p p作为模基数。

2. verifiable secret sharing可验证的秘密共享

Benny Chor等人1985年论文《Verifiable secret sharing and achieving simultaneity in the presence of faults》首次提出了verifiable secret sharing可验证的秘密共享的概念。

2.1 背景介绍

在该论文中，提出了如下场景：同时广播网络中，有n个参与方 A 1 , . . . A n A_1,...A_n A1​,...An​，可容忍t个拜占庭错误。 A 1 , . . . , A n A_1,...,A_n A1​,...,An​ n个人在同一个房间，每个人有自己的黑板和粉笔。房间设置为开灯一个小时，然后关灯一个小时，再开灯一小时，关灯一小时，如此往复。在关灯时，每个人在自己的黑板上写一段话，只有灯亮时，才能同时看到其它人黑板上的内容。在第 j j j次灯关闭时 A i A_i Ai​写的内容，被称为 A i A_i Ai​的第 j j j条消息。 可能存在的场景是，在灯关时，有人偷偷告诉别人即将准备写在黑板上的内容。 所以存在以下属性： 1）在第 j j j轮，假设 A i A_i Ai​不与任何人合作，则 A i A_i Ai​的第 j j j条消息与其它每个人的第 j j j条消息是independent相互独立的；（即时性） 2）当灯亮时，消息不允许擦除或者修改。若 A i A_i Ai​的黑板为空白的，则表示他发送的为空消息。（广播） 3）所有人都可以看到每个人的第 j j j条消息。（广播）

将上述过程抽象为数学描述： 假设 N E T NET NET代表通信网络，该网络中有 n n n个processor 处理器 A 1 , . . . , A n A_1,...,A_n A1​,...,An​ 通过同一消息通道，参与消息的发送和接收。每个参与方除了需要将信息发送给其它人外，还需要进行内部的计算（如抛硬币，读取存储器状态等） 。 若 A i A_i Ai​按指定的协议 P O R T PORT PORT执行，则可说 A i A_i Ai​是正确的，否则称其为错误的。错误的参与方会尝试毁坏整个通信系统。

Simultaneous broadcast networks 即时通信网络是以下协议即时性的核心组成：抛掷硬币，公平选举，合同签订，秘密交换等。

2.2 Verifiable Secret Sharing定义

在Adi Shamir 1979年论文《How to share a secret》中提出的秘密共享方法在信息理论上来说是安全的，但是基于的考虑是所有参与方都是正确的，且消息段的分发是私下地privately。实际应用时，在分布式网络中存在错误的参与方，也没法将消息段以明文形式通过公共网络发送。

当考虑存在不诚实参与方时，对于一个消息段 b i b_i bi​，需要有相应的算法来验证其确实是秘密的有效片段，否则不存在秘密可言。所以Shamir秘密共享机制在需要容错能力的分布式环境中无法使用。

Benny Chor等人1985年论文《Verifiable secret sharing and achieving simultaneity in the presence of faults》提出了具有容错机制的可验证秘密共享算法： 将秘密抽象为一个secret bit b b b， n n n个参与者， t t t个错误，安全参数为 K K K。存在将秘密切分的delaer A和参与者C。

• Part I(准备阶段) 1）获取具有K-bits长度的素数 l l l个—— p 1 , p 2 , . . . , p l p_1,p_2,...,p_l p1​,p2​,...,pl​。 2）计算 N A = p 1 p 2 . . . p l N_A=p_1p_2...p_l NA​=p1​p2​...pl​。 3）选取 x A ∈ R Z N A ∗ x_A\in_RZ_{N_A}^* xA​∈R​ZNA​∗​，使得 x A   m o d   N A x_A\ mod\ N_A xA​ mod NA​的最低有效位为 b b b。 4）计算 y A = x A 3   m o d   N A y_A=x_A^3\ mod\ N_A yA​=xA3​ mod NA​。 5）广播 N A 和 y A N_A和y_A NA​和yA​。

• Part II(数据段分发) 6）通过在A和C之间运行oblivious transfer，每一个参与者C将获得 N A N_A NA​的随机片段。

• Part III（重构秘密） 7）每个参与方C都广播自己所拥有的 N A N_A NA​片段。 8）参与方C可验证A是否背离了协议，若发现A不诚实，则设置b=“empty message”；若诚实，则C继续接收 N A N_A NA​的其它数据片段（至少 n − t n-t n−t个），然后尝试对 N A N_A NA​进行因式分解。若 N A N_A NA​可被分解，且正好有 l l l个素数因子，且the exponent 3 is relative prime to φ ( N A ) \varphi(N_A) φ(NA​)，则C可计算 x A = y A 3   m o d   N A x_A=\sqrt[3]{y_A}\ mod\ N_A xA​=3yA​ ​ mod NA​，取 x A x_A xA​的最低有效位即为A要共享的秘密 b b b。

3. Feldman Verifiable Secret Sharing(Feldman VSS算法)

Paul Feldman 1997年论文《A Practical Scheme for Non-interactive Verifiable Secret Sharing》是第一个有效的VSS算法。

参考资料： [1] 1991年论文《non-interactive and information-theoretic secure verifiable secret sharing》 [2] 1979年论文《How to share a secret》 [3] 1997年论文《A Practical Scheme for Non-interactive Verifiable Secret Sharing》 [4] 1985年论文《Verifiable secret sharing and achieving simultaneity in the presence of faults》 [5] 1979年论文《Safeguarding cryptographic keys 》 [6] 1998年论文《Proactive Secret Sharing Or: How to Cope With Perpetual Leakage》 [7] https://en.wikipedia.org/wiki/Verifiable_secret_sharing