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

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

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协议均考虑同步网络模型。

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学习小组与小伙伴们一起学习~

往期推荐