笔记分享 | 冯登国院士MPC讲座（2）——基于秘密分享方法的安全多方计算协议

代入b = 0 和b = 1，可以验证结果的正确性。

除此之外，COT还可以变形为量不经意线性函数计算，OT可以变形为不经意线性函数计算。

诚实大多数半诚实安全MPC协议

接下来冯院士正式开始讲解关于秘密分享的内容。第一讲中，冯院士已经介绍了秘密分享协议的相关概念，依照下图进行一个简单回顾：

LSSS（linear secret share scheme）线性秘密分享方案包括三个算法，分享算法、重构算法、打开算法，其中打开算法是让每个参与方都运行一次重构算法便能够让所有参与方获得秘密值。

秘密分享的线性性质意味着参与方可以利用本地拥有的份额进行加法门、数乘门的计算，不需要与其他参与方进行交互、通信。对于乘法门运算，需要参与方们进行交互，运行乘法子协议。

线性秘密分享的MPC协议的一些知识点：

• 支持多个参与方运行协议；若腐化门限，通信复杂度一般为，若，通信复杂度一般为；

• 加法和数乘等线性门无需通信，计算速度极快； 

• 协议通信主要发生在乘法门计算； 

• 所有运算定义在有限域上，也可推广至一般环上(根据应用，环通常考虑剩余类环)，由于模运算等价于直接截断)；

• 基于线性秘密分享的MPC协议主要考虑如何设计实际高效的乘法子协议；

接下来介绍了诚实大多数半诚实安全的MPC协议，回顾一下诚实大多数意味着被腐化的参与方数量, 而半诚实安全意味着所有参与方都是遵守协议进行计算，但是会利用已有的信息推断其他参与方的隐私信息.

基于Shamir秘密分享的协议是很常见的，上一讲中也有所介绍，主要思路就是通过选取次数为的随机多项式进行秘密值的分享。通过拉格朗日插值法也可以恢复出秘密值，即重构。

除了上述这种先选择多项式后生成份额的方法，还有另外一种生成方式：

这种方式就是先选择几个随机值当作份额，再根据秘密值构造一个多项式，最后生成其他份额。

上述的方法可以利用PRG伪随机数生成器进行优化，降低通信开销。

主要思想：关键就是发送的随机种子可以用于多次，这样就可以让个参与方自己计算出自己的的份额，而就只用给剩下的个参与方发送份额即可，所以通信开销降低为个域元素。

随机值的Shamir秘密分享生成

很多协议都应用了随机值的秘密份额，那这种随机值的份额是如何生成的呢？

第一种方法：

1. 每个参与方自己本地选择一个随机数，然后把这个随机数分享给其他参与方；

2. 每个参与方本地计算这些随机数的份额的加和，就相当于得到了所有随机数加和的份额。

如果想要获得多个随机值的份额，可以应用第二种方法：

1. 各方首先随机选取一个元素，然后再秘密分享给其他参与方。

2. 各方手里有n个份额，再与范德蒙矩阵进行相乘操作即可得到n-t个随机值的份额。

由于n-t个参与方都是诚实的，这就保证了每个参与方获得的的n-t个份额就是n-t个随机值的秘密分享。

秘密分享协议中进行乘法运算的子协议

第一种方法：

由于一开始进行秘密分享时，选择的多项式都是t次的，所以再乘法运算时，会导致多项式次数变为2t次，因此乘法门计算中需要降次操作。

第二种方法：

第三种方法：

这种方法用到了前面提到的生成随机值的秘密分享的方法，生成随机双分享（相同的随机值，一个是t次分享份额，一个是2t次分享份额）。注意，由于引入了随机值，所以公开并不会泄露的值。

2020年提出了一个优化的DN乘法子协议：

与原始的方法区别就是：并不直接发送公开的e，而是对e做一个t次的秘密分享，再把份额发送给其他参与方。

2021年美密会上提出了一个方法进一步优化了DN乘法子协议ATLAS：

对综上的协议做一个比较，如图：

以上讲的协议都是针对敌手是半诚实的情况，那么当敌手是恶意时，我们应该如何构造协议保证安全性？这里主要涉及到乘法验证技术。

诚实大多数假设下乘法验证技术

在诚实大多数假设下大部分半诚实安全的乘法子协议，例如上面提到的DN类乘法子协议，满足以下性质：

• 在恶意敌手模型下已经保证了输入/输出的隐私性 

• 但不能保证计算的正确性，即允许敌手在输出中引入加法错误，如下： 对于输入份额，输出份额为, 其中是敌手选择的加法错误。

因此，在恶意敌手模型下诚实大多数MPC协议的主要目标是设计高效的乘法验证协议，保证在所有乘法门输出中加法错误为0（即没有错误被引入）。

在诚实大多数假设下，主要有以下三种乘法验证技术，通信开销如图所示：

冯院士主要讲解了对偶验证技术：

主要思路：运行两次半诚实安全的协议，两次协议分享的输入不同，一个是真实输入值，另一个是随机化输入，在通过两个协议的执行结果验证乘法计算正确性，如果验证通过，就可以通过重构算法输出结果。

具体操作： 

1. 首先所有参与方执行随机值的分享生成协议，获得一个随机值的份额。对于每个电路的输入，所有参与方不仅获得真实值的秘密分享份额，还要利用乘法子协议计算的份额。同理，真实值也是一样。 

2. 参与方利用手里拥有的份额计算和。 

3. 参与方利用和计算。 

4. 通过分享检查 和 是否相等，如果不相等则说明敌手引入了误差，而相等的时候可以以的概率认为协议是正确执行的。我的理解是由于是均匀随机的且敌手不知道，那么恰好等于的概率最大为，当域很大的时候，这个概率是可忽略的。

上述方法本来是要进行一次乘法子协议得到，但是运行了额外两次乘法子协议来验证，增大了计算和通信开销，下面提出一种优化的方法：

设有m个乘法门需要计算并检验，首先参与方们运行投币协议，生成m个随机系数。相比于运行乘法子协议计算, 本方法选择了执行打开算法公开，在本地计算的方法，减少了一次乘法子协议带来的计算和通信开销。

上述方法都有一个共同的步骤那就是“检查相等“，这里需要注意，两个秘密值相等但他们秘密分享的份额不一定相等，那要如何在不暴露秘密值的情况下根据秘密份额检查相等呢？

可以用下面的方法：

1. 所有参与方运行秘密值的分享生成协议，获得一个秘密值的分享份额。 

2. 参与方本地计算， 和 是要检查的两个秘密值。

3. 参与方运行乘法子协议，得到，再运行打开算法得到。 

4. 这时就可以通过验证是否等于0，来判断是否等于0，进而判断出是否等于。考虑到的随机性的情况，敌手引入加法误差的时候仅能以的概率通过检测，当域很大时，这个概率是可忽略的。

半诚实安全GMW协议及其优化

GMW协议是针对布尔电路的秘密分享协议，秘密分享的方式是加法秘密分享。

其中异或运算是参与方在本地就可以完成的，但是与运算需要借助4选1的不经意传输完成。

优化方法：采用2选1的不经意传输协议替换4选1的不经意传输协议，可以降低单向通信开销至少2倍。

通过拆解计算过程，发现有的结果可以在本地计算，剩下的部分只需要用2选1的OT计算即可。

另外上述的两方GMW协议可以推广至多方场景，也可以从布尔电路推广至算术电路。

接下来冯院士讲解了如何用Beaver三元组技术实现GMW的在线/离线阶段。

当电路未知时：

当电路已知时：

以上是冯登国院士MPC讲座第二讲的内容笔记，4月22日本周六将会进行第三讲——基于混淆电路方法的MPC协议。详情请点击MPC课程 | 跟着院士学隐私计算了解讲座信息，同时加入我们的MPC学习小组与小伙伴们一起学习~

往期推荐