笔记分享 | 冯登国院士MPC讲座（1）——MPC基本概念和基础组件

本文作为学习笔记整理了2023年3月25日，冯登国院士的MPC讲座第一讲的内容。讲座总共分为三讲，第一讲是MPC基本概念及基础组件，第二讲是基于秘密分享方法的MPC协议，最后一讲是基于混淆电路方法的MPC协议。冯登国院士是我国网络与信息安全的专家，主要从事保密通信、网络安全和可信计算等理论与技术的研究。了解后续讲座信息，请点击MPC课程 | 跟着院士学隐私计算查看。本文如果有错误的地方欢迎指正~

1

MPC定义与应用

冯院士首先以一个五方计算为例，解释了多方安全计算的两条重要性质：隐私性和正确性。 

• 隐私性意味着除了五方一起计算的函数的输出以外，这五方中的任意一方的数据都不会泄露。
• 正确性则保证了五方执行的协议输出的结果就是他们想要计算的函数的结果。

如何定义MPC的安全性呢？ 几乎所有的MPC协议都采用了基于模拟的安全模型来定义协议的安全性。 具体来说： 有两个模型，一个是现实模型，一个是理想模型。现实模型中就是参与方们通过MPC协议交互并计算目标函数。在理想模型中，存在一个可信的第三方，参与方只要将数据发送给这个可信第三方，它进行计算后再把结果返回给参与方。显而易见，理想模型自然就是安全的。那么在安全证明中如何证明呢？基本思想就是要证明设计的现实世界的协议和理想世界的计算是概率不可区分的，这样就可以借助理想世界的安全性证明现实世界的安全性，即MPC协议的安全性。正式的证明方法可以参考书籍: 《Foundations of Cryptography》接着冯院士介绍了安全多方计算的发展阶段，从亿万富翁财产比较问题到如今的实际安全协议设计，MPC已经经过了近40年的发展。其中，很多经典的协议都是早在上世纪80年代设计的。后来的协议都对这些协议进行了改进，提高了效率或者增强了安全性等。目前，MPC的应用领域十分广阔，例如政务、金融、医疗等。目前数据安全问题受到很大重视，无论是个人对隐私信息的重视还是国家颁布了相关的法律法规都可以看出，实现数据可用不可见是很重要的。
2

MPC的分类

按照不同的分类标准可以将MPC进行不同的分类： 

• 按照敌手行为可以分类： 

半诚实敌手(Semi-honest)：按照协议描述执行，但试图从协议记录中获取信息，也称作被动的。

恶意敌手(Malicious)：可以执行任何攻击，发送任意的消息，也称作主动的。

• 按照腐化门限分类(是参与方的数量，是被腐化的参与方的数量)：

诚实大多数(Honest majority): 。 

不诚实大多数(Dishonest majority): 。

• 按照输出可达性分类： 

中止安全(Security with abort)：腐化实体获得输出后，可以阻止诚实实体获得输出。

公平性(Fairness)：要么腐化实体和诚实实体均获得输出，要么他们均没有输出。

保证输出传送(Guaranteed output delivery)：所有诚实实体总是获得输出。

一般而言，不诚实大多数情况仅能达到中止安全；诚实大多数情况能达到公平性和保证输出传送。

• 按照计算模型分类： 

布尔电路：由AND、XOR、NOT等逻辑门组成 。

算术电路：由ADD、MULT等运算组成，通常定义在域上或环(即上)。

RAM程序：由read、write等指令组成的程序。

• 按照敌手计算能力分类： 

概率多项式时间（PPT）：任意PPT敌手不能打破协议安全性。

无限计算能力（信息论安全或无条件安全）：即使无限计算能力的敌手也不能打破协议安全性（抵抗量子计算机攻击）。

信息论安全MPC协议需要在诚实大多数模型下设计。

• 按照腐化策略分类： 

静态腐化（Static Corruption）：在协议运行前，敌手决定腐化哪些实体。

自适应腐化（Adaptive Corruption）：在协议运行过程中，敌手能够自适应决定腐化哪些实体。

• 按照网络模型分类： 

同步（synchronous）网络模型：同一个交互轮的消息在固定延时内一定到达。

异步(asynchronous)网络模型：没有要求同步时钟，也没有要求预先固定的网络延时，更加现实的网络假设（通常要求)。

已知高效的MPC协议均考虑同步网络模型。

3

MPC的基础组件

高效的MPC协议会利用到图中所表示的基础组件：

线性秘密分享

首先是线性秘密分享，如图所示，每个参与方将自己的秘密值通过秘密分享的方式分享给其他参与方，这种方式可以保证秘密份额不能暴露秘密的信息，同时只有当收集到一定份额数时才能还原出秘密，所以称为门限秘密分享。

常见的秘密分享协议包括三种：Shamir 秘密分享、加性秘密分享、复制秘密分享。老师会在后续的讲座中重点讲解基于秘密分享的协议。

可以看到不同的协议，它们应用的场景不同，我们在选择应用哪种协议时要考虑清楚自己问题的定义。

考虑作恶的参与方会将不正确的share分享给其他参与方，所以引入认证性，不同的协议采用不同的认证方法就能够验证share是否正确。

例如，当采用加法秘密分享时，通过不同的IT-MAC进行验证，可以分为BDOZ和SPDZ两种协议。这里也只是简单说明了有这样的概念，后续讲座会重点介绍。

零知识证明

零知识证明也是MPC的基础组件之一，通常分为证明者和验证者两方，证明者想要向验证者证明某个定理，但是又不暴露自己的证据。

零知识证明具备以下性质：

完备性(Completeness)：验证者无法欺骗证明者。若证明者知道一个定理的证明方法，则它可以使验证者以绝对优势的概率相信他能证明。

可靠性(Soundness)：证明者无法欺骗验证者。若证明者不知道一个定理的证明方法，则证明者使验证者相信他会证明定理的概率很低。

零知识性(Zero Knowledge)：验证者无法获得任何额外的知识。

混淆电路

混淆电路也是实现MPC的重要方法之一。参与方分为混淆方和评估方，大致过程如下：

1. 混淆方：对输入进行编码、用编码信息作为密钥加密电路真值表再打乱顺序。

2. 评估方通过不经意传输选择自己输入的对应编码。

3. 混淆方将自己的输入编码和混淆表发送给评估方。

4. 评估方利用输入的编码解密混淆表，最后将结果发送给混淆方。

5. 混淆方对结果进行解码，得到电路计算结果。

其他组件

不经意传输

不经意传输的最简单的例子如上图所示，参与方分为发送者和接收者，1-out-of-2 OT就是发送者拥有两个秘密，接收者想要其中一个，不经意传输保证了发送者不知道接收者选择的是哪个，而接收者除了接收到自己想要的秘密，不能获得另外一个秘密的信息。1-out-of-N OT同理，只不过是发送者拥有N个秘密。

基本的实现方式如下图所示：

但是不经意传输需要公钥密码的操作，所以效率上会存在问题。作为MPC的基础组件，当需要执行的OT操作很多时，会导致协议的效率过低。于是引入了OT 拓展的方法来解决，具体也分为以下几类：IKNP类、PCG类、PCF类。

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

END

​

往期推荐

1.全同态加密知识体系整理(下)
2.PSI系列（2）组件 | OT Extension (IKNP)3.PSI系列（1）组件 | Cuckoo Hashing4.全同态加密知识体系整理(上)