多方安全计算知识点整理——秘密分享

秘密分享定义如下：秘密持有者 需要将原始秘密 在参与者集合中 ，使得只有特定参与者的集合才能够从他们的子秘密中恢复秘密 ，而其他参与者不能得到秘密 的任何信息。

能够计算出秘密 的参与者集合 的一个子集 ，称为一个授权子集。令 为所有授权子集构成的集合，则称 访问结构。

秘密分享方案一般描述如下：将分享的秘密 分割成 个子秘密，并将其分发至 个参与者，使得授权子集 中的参与者可共同恢出复秘密 ，而非授权子集中的参与者无法得到关于秘密 的任何信息。

Adi Shamir于1979年提出了基于拉格朗日(Lagrange)插值定理的 -门限方案。该方案利用有限域上的次随机多项式来分享秘密，被分享的秘密为多项式的零次系数，恢复秘密至少需要 个多项式上的点。

方案描述如下：

设  是一个有限域,   为公开大素数, 分享的密钥 , 可信中心给   个分享者 分配分享的过程如下:

(1) 秘密分发

可信中心随机选取多项式   , 常数 为要分享的秘密。

可信中心在  中选择  个非零的互不相同的 元素   , 计算   , 将子密钥   分配给分享者   是公开的,   为 的秘密分享)。

(2) 秘密重构

给定  个分享   , 从Lagrange多项式重构的

其中,   (Lagrange插值系数), 运算都是 上的运算。

例子：

设   , 随机选取   , 得多项式为

选择 ，则由 ，，很容易得到 5 个子密钥

如果知道其中 3 个子密钥  ，则

从而解得 。

Asmuth和Bloom于1980年提出了一个基于中国剩余定理的 -门限方案。该方案中，成员的分享是由秘密 得出的数  对于不同模数   的剩余。

令   是满足下列条件的一组正整数:

对所有的 ;

对  

令   是 个最小整数之积，则 大于任意    个    。令  是区间    中的一个随机整数, 并公布  。

(1) 秘密分发

将  划分为    个分享, 计算   , 则   。 个分享 为 , 将子密钥   分配给分享者 。

(2) 秘密重构

若给定   个分享   , 则由中国剩余定理可知, 同余方程组

关于模 在    内有唯一解   , 因为 , 推出   。最后计算出 , 即   。

例子：

设 , 则

在    之间随机取   ,

3 个子密钥为 。

若知道 , 可建立方程组:

根据中国剩余定理，解得：

因此  。

可验证的秘密分享VSS方案是对传统秘密分享方案的修正，在通常的秘密分享方案基础上附加验证操作构成，主要用于解决不诚实的分发中心问题。

在VSS方案中，分发者不但分发秘密的碎片，而且广播对秘密碎片的承诺，当个成员收到其碎片时，要验证其碎片是否正确；在秘密重构阶段，每个参与者也采用同样方法验证其他成员秘密碎片的正确性。

VSS主要抵抗以下两种主动攻击：

• 分发者在秘密分发协议中发送错误碎片给部分或全部参与者。 

• 协议参与者在秘密重构协议中提交错误碎片。 

常见的可验证的秘密分享方案包括Feldman的VSS方案以及Pedersen方案。

4.1 Feldman的VSS方案 

(1) 秘密分发

可信中心选取阶随机多项式：

常数 为要分发的秘密;

可信中心选择 个非零的互不相同的元素 ，计算 , 将子密钥    分配给分享者 ( 是公开的, 为 的秘密分享)，可信中心计算并广播承诺 。

参与者 收到自己的碎片 后, 判断 是否成立, 如果成立, 则接受该碎片为有效; 否则,  请求可信中心重新发送正确的碎片。

若可信中心向    传送了正确的碎片 , 则有

(2) 秘密重构

假设每个参与者都接受到正确的碎片, 他们中的任意   个可执行 Shamir门限秘密分享方案中的重构算法恢复出院时秘密, 即   向参与重构的其他人广播自己的碎片，这样每个参与重构的成员均可验证所接收到的碎片的有效性，然后使用Lagrange揷值公式计算出秘密   。

Feldman的VSS方案中, 由于可信中心在广播承诺时将    也作为一个承诺发出, 因此方案仅是计算安全的。

4.2 Pedersen的VSS方案 

Pedersen扩展了Feldman的方案，将Shamir秘密分享方案与承诺方案相结合，构造出了一个高效、安全的非交互式可验证秘密分享方案，且验证信息不会直接泄露秘密 ，因此是信息论安全的。

(1) 秘密分发

可信中心选取两个 阶随机多项式：

常数 为要分发的秘密。

可信中心选择 个非零的互不相同的元素   ,计算   将子密钥 分配给分享者 ( 是公开的, 为 的秘密分享)。可信中心计算并广播承诺 。

参与者  收到自己的碎片   后, 判断 是否成立。如果成立, 则接受 该碎片为有效; 否则, 请求可信中心重新发送正确的碎片。

若可信中心向 传送了正确的碎片 , 则有

(2) 秘密重构

假设每个参与者都接受到正确的碎片, 他们中的任意 个可执行 Shamir门限秘密分享方案中的重构算法恢复出原始秘密, 即 向参与重构的其他人广播自己的碎片, 这样每个参与重构的成员均可验证所接收到的碎片的有效性, 然后使用Lagrange揷值公式计算出秘密  。

Pedersen的VSS方案中，可信中心在广播承诺时与秘密 相关的信息仅为 ，没有泄露关于 的任何信息，因此方案是信息论安全的。

在该秘密体制中不存在秘密分发者，仅有参与者 ，他们以交互的方式协商出一个随机秘密 ，并各自得到该秘密的一个碎片 ，但每个参与者都不知道这个随机秘密的具体值，除非他们公布自己的碎片并重构该秘密。

基于Shamir的秘密分享体制的一个无秘密分发者的 秘密分享体制，称为Joint-Shamir-RSS方案（Joint Shamir Random Secret Sharing）。

(1) 每个参与者   选择一个    次随机多项式   , 以   作为自己要让   分享的秘密。

(2) 计算   , 发送给   , 如下所示:

(3) 收到其他参与者的值 计算    作为自己最终分享秘密的碎片。

从协议中可以看出, 若令 , 则  。

秘密重构阶段，只需任意 个参与者使用自己拥有的秘密碎片 执行Shamir秘密分享体制的秘密重构即可。

对秘密分享技术感兴趣的小伙伴，可以点击查看笔记分享 | 冯登国院士MPC讲座（2）——基于秘密分享方法的安全多方计算协议。

往期推荐