多方安全计算知识点整理——秘密分享
目录
1. 秘密分享简介
2. Shamir 秘密分享方案
3. Asmuth-Bloom方案
4. 可验证的秘密分享
4.1 Feldman的VSS方案
4.2 Pedersen的VSS方案
5. 无分发者的随机秘密分享
秘密分享简介
秘密分享通过将秘密以适当的方式拆分，拆分后的每一个份额由不同的参与者管理，单个参与者无法恢复秘密信息，只有若干个参与者一同协作才能恢复秘密消息。
秘密分享定义如下：秘密持有者 需要将原始秘密 在参与者集合中 ，使得只有特定参与者的集合才能够从他们的子秘密中恢复秘密 ，而其他参与者不能得到秘密 的任何信息。
能够计算出秘密 的参与者集合 的一个子集 ，称为一个授权子集。令 为所有授权子集构成的集合，则称 访问结构。
秘密分享方案一般描述如下：将分享的秘密 分割成 个子秘密，并将其分发至 个参与者，使得授权子集 中的参与者可共同恢出复秘密 ，而非授权子集中的参与者无法得到关于秘密 的任何信息。
Shamir秘密分享方案
Adi Shamir于1979年提出了基于拉格朗日(Lagrange)插值定理的 -门限方案。该方案利用有限域上的次随机多项式来分享秘密，被分享的秘密为多项式的零次系数，恢复秘密至少需要 个多项式上的点。
方案描述如下：
设 是一个有限域, 为公开大素数, 分享的密钥 , 可信中心给 个分享者 分配分享的过程如下:
(1) 秘密分发
可信中心随机选取多项式 , 常数 为要分享的秘密。
可信中心在 中选择 个非零的互不相同的 元素 , 计算 , 将子密钥 分配给分享者 是公开的, 为 的秘密分享)。
(2) 秘密重构
给定 个分享 , 从Lagrange多项式重构的
其中, (Lagrange插值系数), 运算都是 上的运算。
例子：
设 , 随机选取 , 得多项式为
选择 ，则由 ，，很容易得到 5 个子密钥
如果知道其中 3 个子密钥
从而解得 。
3
Asmuth-Bloom方案
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）——基于秘密分享方法的安全多方计算协议。
本文作者：无忧
CSDN链接：
https://viper.blog.csdn.net/article/details/128889028
往期推荐
1.论文分享 | 基于LWE(Learning with Error)的高效联邦学习安全聚合
2.密码学中的模乘算法——巴雷特模乘(Barrett Modular Multiplication)3.pFedPT：将prompt学习融入进联邦学习4.密码学中的模乘算法——蒙哥马利模乘（Montgomery Modular Multiplication）