笔记分享 | 冯登国院士MPC讲座（3）——基于混淆电路方法的安全多方计算协议

本文作为学习笔记整理了2023年4月22日，冯登国院士的MPC讲座第三讲的内容。讲座总共分为三讲，第一讲的笔记可以查看MPC基本概念及基础组件，第二讲笔记可以查看基于秘密分享方法的MPC协议。冯登国院士是我国网络与信息安全的专家，主要从事保密通信、网络安全和可信计算等理论与技术的研究。本文如果有错误的地方欢迎指正~

1

恶意安全SPDZ协议

冯院士首先针对第二讲中剩下的一个小节（恶意安全SPDZ协议）进行讲解。上一讲中讲到的大部分协议都是针对半诚实敌手的，通过通信编译器可以转化半诚实安全协议为恶意安全协议。编译器主要用两种：

• GMW编译器，采用零知识证明技术（非黑箱构造）证明每条消息的正确性 
• IPS编译器，采取两层协议，内层运行半诚实安全不诚实大多数MPC协议，外层运行恶意安全诚实大多数MPC协议（黑箱构造）

这种编译器的实际效率均偏低。目前实际高效不诚实大多数MPC协议主要采用IT-MACs达到恶意安全性。下面要介绍的SPDZ协议，就是采用IT-MACs加强半诚实安全GMW协议至恶意安全，并且能够容忍腐化门限。具体的：上述敌手能够伪造不同消息的消息认证码的概率为，当够大时，上述概率是可忽略的。打开1个认证分享的步骤如图所示：这里用到了CheckZero子协议去检查认证分享值为0，具体的: 每方承诺自己的，然后打开承诺公开，验证。（因为, 所以当秘密值为0时，为0）

批量打开  个SPDZ认证分享的步骤如图所示：

重点就是如何打开 个秘密值后，进行批量验证零认证分享。为了减小通信复杂度，可以采用投币协议生成 个随机值（常数轮通信复杂度），各方本地计算（不需要通信），由于是零认证分享，所以只要验证线性组合的结果是否为零认证分享即可。

SPDZ协议中认证三元组的生成

认证三元组是秘密分享中乘法子协议中常用的组件，但是在SPDZ协议中，认证三元组的生成是效率瓶颈。

认证三元组满足。主要分为三种情况：大域、二元域、整数环。

在恶意敌手安全条件下，参与方可以偏离协议，所以需要验证认证三元组的正确性，有以下方法：

• 大域或整数环:主要采用牺牲方法等 

• 二元域：主要采用Cut-and-Choose和Bucketing方法、RMFE方法等

下面介绍一下牺牲方法：

左边是验证三元组和牺牲三元组中有一个秘密值相同的情况，右边是两个三元组之间没有相同的秘密值的情况，右边的情况需要多打开一个值。安全性的分析和左边类似，当够大时，敌手的攻击也是可忽略的。

有了上述的准备工作，我们可以看一下完整的SPDZ协议：

协议分为两个阶段：

预处理阶段（离线阶段）：为每个乘法门生成认证三元组，为每条输入线生成随机认证分享。

在线阶段：计算电路。

2

基于混淆方法的MPC协议

接下来冯院士开始讲解本讲内容——基于混淆电路方法的MPC协议，主要介绍安全两方计算（2PC）协议的设计方法，重点设计混淆电路的构造方法。

Yao的半诚实安全两方计算协议

首先回顾在第一讲中已经简单介绍过的Yao 的半诚实安全两方计算协议

两方分为混淆方和计算方，两方分别有秘密值，想要计算。 

离线阶段： 

混淆方运行混淆算法Garble生成混淆电路F和编码信息e和解码信息d，并把F，d发送给计算方。 

在线阶段： 

• 双方运行OT协议，混淆方作为发送方，计算方作为接收方。

• 计算方输入可获得编码后的值。 

• 混淆方将编码后的值发送给计算方。

• 计算方利用计算混淆电路G, 最后利用d进行解码得到最终的结果。

下图展示了混淆电路的基础框架，形式化了混淆算法、编码算法、解码算法、计算算法。

下面我们来看一下是如何混淆单个计算门的。

对电路门的输入线和输出线进行编码，利用输入值的编码计算电路得到输出值的编码。

Textbook Yao的混淆方法

以与门为例，首先构造与门的真值表，然后将真值表中的数字用对应的编码信息代替，并利用输入线的编码L、R作为密钥加密输出线的编码Z。

具体的加密方法如下所示：

如果想要判断解密是否正确，可以通过添加0比特序列的方式，当解密结果包括0比特序列时，可以认为密文解密正确。

上述的方法中，计算方在解密时，需要解密混淆表中的每一行，然后根据结果判断自己是否得到了正确的计算结果，然后再进行下一步的计算，这样的效率过低。

点置换优化算法

下面介绍的点置换优化算法(Point-and-Permute)不仅可以降低通信开销也可以减少计算方的平均解密次数。

方法：

混淆方在混淆电路时，为每个计算门的输入线、输出线上的编码信息添加随机置换比特，再根据公开比特构造混淆表。

通过上图所示构造出混淆电路后，计算方在计算混淆电路时，通过公开比特计算混淆电路表的特定行即可得到正确的解密结果以及结果的公开比特。

通过点置换优化可以大大降低开销：

除此之外，通过选择加密算法中不同的，也可以改进混淆电路的计算效率：

混淆行约化技术

通过混淆行约化技术（Garbled Row Reduction）可以进一步减小通信开销：

我理解的思路就是将输出线的编码信息等于，这样这一行的加密结果就是0比特串，只需要通信其他3行即可，减小了通信开销。（老师讲的例子里是对进行了这样的处理，不知道对其他行是否也可以）

Free XOR技术

在线性秘密分享协议中，加法门的运算不需要参与方进行通信，只需要本地计算即可，被称为 “free” 特性。在混淆电路协议中，通过Free XOR技术也可以实现电路中XOR门的 “free”。

上图中的为全局密钥，满足固定相关性。

通过Free XOR技术，可以大大降低XOR门的通信开销，因为不需要通信XOR门的混淆表。

正确性验证如下图红色部分计算可以证明：

还有一些改进工作，感兴趣的同学可以阅读相关文献：

3

推荐阅读

到此为止，冯院士的三次讲座都已结束，这里推荐给大家三篇MPC综述论文。

论文链接分别为：

• https://eprint.iacr.org/2020/300

• https://eprint.iacr.org/2022/417

• https://sands.edpsciences.org/articles/sands/full_html/2022/01/sands20210001/sands20210001.html

想要进一步了解冯院士论文的小伙伴，也可以访问冯登国院士团队重磅论文！《具体高效的安全多方计算协议综述》解读学习~

END

往期推荐

1.一文搞懂分组密码——DES、AES、IDEA
2.Turbospeedz: 使用函数相关预处理技术提高SPDZ协议在线效率3.技术分享 | 隐私集合求交（PSI）技术体系整理4.联邦学习算法分类总结