开放隐私计算

0

目录

1. 秘密分享简介

2. Shamir 秘密分享方案

3. Asmuth-Bloom方案

4. 可验证的秘密分享

4.1 Feldman的VSS方案

4.2 Pedersen的VSS方案

5. 无分发者的随机秘密分享

1

秘密分享简介

秘密分享通过将秘密以适当的方式拆分，拆分后的每一个份额由不同的参与者管理，单个参与者无法恢复秘密信息，只有若干个参与者一同协作才能恢复秘密消息。

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

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

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

2

Shamir秘密分享方案

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

方案描述如下：

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

(1) 秘密分发

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

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

(2) 秘密重构

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

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

例子：

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

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

如果知道其中 3 个子密钥

，则

从而解得 。

3

Asmuth-Bloom方案

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

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

对所有的 ;

对

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

(1) 秘密分发

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

(2) 秘密重构

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

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

例子：

设 , 则

在 之间随机取 ,

3 个子密钥为 。

若知道 , 可建立方程组:

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

因此 。

4

可验证的秘密分享

可验证的秘密分享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方案中，可信中心在广播承诺时与秘密 相关的信息仅为 ，没有泄露关于 的任何信息，因此方案是信息论安全的。

5

无分发者的随机秘密分享

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

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

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

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

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

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

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

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

本文作者：无忧

CSDN链接：

作者简介：无忧，毕业于北京邮电大学，目前就职于华为技术有限公司， 长期从事信息安全、密码学领域研究。