安全多方计算简介

安全多方计算

安全多方计算（SecureMulti-partComputation,MPC）是80年代提出的一个概念，它已成为隐私计算的核心技术之一。在密码学和区块链技术应用中占据重要地位。

MPC数学定义：

假设存在n个参与方$P_1,P_2,\dots ,P_n$，每个参与方都有一个私有输入数据$x$，所有参与方共同计算某个函数$f(x_1,x_2,\dots ,x_n)$，且要求在计算结束时，每个参与方$P_i$只能得到私有输入数据$x_i$的输出，而不能获取其他参与方的输入信息及输出结果信息。

公式：
$$(y_1,y_2,\dots ,y_n)=f(x_1,x_2,\dots ,x_n)$$
基本要求：

• 隐私性：除了函数输出外，不泄露任何输入数据的信息
• 正确性：保证协议输出为指定函数的结算结果

安全多方计算分类

1. 不诚实参与方的数量占比

   • 诚实大多数：诚实参与方占据大多数
   • 不诚实大多数：不诚实参与方占据大多数

   

2. 敌手行为

   • 半诚实敌手：按照协议描述执行，但试图从协议记录中获取信息
   • 恶意敌手：可以执行任何攻击，发送任意的消息

3. 输出可达性

   • 中止安全（Security with abort）：恶意实体获得输出后，可终止协议使得诚实实体不能获得输出
   • 公平性（Fairness）：如果一个实体获得输出，那么所有实体获得输出
   • 保证输出传送（Guaranteed output delivery）：所有实体一定获得输出

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

4. 计算模型

   • 布尔电路：由逻辑门（AND、XOR）等组成的电路
   • 算数电路：域/环上操作（ADD、MULT）成的电路
   • RAM程序：由Read、Write等指令组成的程序

   

5. 敌手计算能力

   • 概率多项式时间（Probabilistic Polynomial Time）：任意PPT敌手不能打破协议安全
   • 无限计算能力（信息论安全或无条件安全）：即使无限计算能力的敌手也不能打破协议安全性 （抵抗量子计算机攻击）

   熟悉密码学的同学应该对这两个名词不会感到陌生。信息论安全MPC协议需要在诚实大多数模型下设计。

6. 腐化策略

   腐化策略指的是攻击者确定攻破并控制参与方的策略。下面给出两种腐化策略：

   • 静态腐化（Static Corruption）：在协议运行前，敌手决定腐化（Corrupt）哪些实体
   • 自适应腐化（Adaptive Corruption）：在协议运行过程中，敌手能自适应决定腐化哪些实体

   对比密码学中的适应性选择明文攻击和非适应性选择明文攻击可以看出，自适应腐化比静态腐化更强。

7. 通信网络

   • 同步（Synchronous）网络模型：在一个交互轮的消息在固定延时$\Delta$一定到达
   • 异步（Asynchronous）网络模型：没有要求同步时钟，也没有要求预先固定的网络延时，更加现实的网络假设

安全多方计算基础组件

以上是安全多方计算基础组件图。这里简单介绍零知识证明，同态加密。

零知识证明

零知识证明（ZKP，Zero-Knowledge Proof）是一种新兴的密码学工具，证明者（prover）可以用其向验证者（verifier）证明某个声明，而不泄露其他额外的信息。

打个比方，如果我有一个很复杂的拼图需要完成，但我知道靠我的能力完成这个拼图会非常艰难甚至说根本拼不出来，这时我就需要找一个擅长拼图，能把我的拼图拼好的人来帮我。这时来了一个人，他跟你说他能完成这个拼图，只要你给他一笔报酬。你当然不会轻易相信他说的话，于是你要先让他证明他有这个拼图的能力。

如何证明呢？这就是问题的关键，最简单的想法就是当着你面让他把拼图拼好。但对方不愿意这样做，因为在他拼图的过程中，他可能会用到自己的“独家秘笈”，而这个他是绝对不愿意让别人看到的。于是，只能在不暴露他的特技的情况下证明他有这个能力。在这种情况下的证明就是所谓的零知识证明。

现实生活中的例子（以身份认证系统为例）：

零知识证明三大性质：

1. 完备性（Completeness）：若声明是真，那么验证者总是接受证明
2. 可靠性（Soundness）：若声明为假，则验证者总是拒绝证明
3. 零知识（Zero-Knowledge）：即验证者无法从该证明过程中获取额外的信息

不同的零知识性：

1. 完美的零知识性（Perfet Zero-Knowledge)：在这个协议中，证明者泄露给验证者的额外信息是0
2. 统计学的零知识性（StatisticalZero-Knowledge）：在整个协议中，证明者泄露给验证者的额外信息是可忽略的
3. 基于算力假设的零知识性 (Computational Zero-Knowledge)：在任意一个随机多项式时间内，在整个协议中，证明者泄露给验证者的额外信息是可忽略的

同态加密

无论是在密码学的课上，还是在信息论的课上，同态加密都会被讲到。同态加密的概念也并不复杂，它就是一类具有特殊属性的加密方法。

与一般加密算法相比，同态加密除了能实现基本的加密操作之外，还能实现密文间的多种计算功能，即先计算后解密可等价于先解密后计算。下图是一个典型的加法同态的例子：

同态加密研究较为深入的是加法同态和乘法同态。

• 加法同态：如果存在有效算法$\oplus$，$E(x+y)=E(x)\oplus E(y)$或者$x+y=D(E(x)\oplus E(y))$成立，并且不泄漏x和y。
• 乘法同态：如果存在有效算法$\otimes$，$E(x\times y)=E(x)\otimes E(y)$或者$x\times y=D(E(x)\otimes E(y))$成立，并且不泄漏x和y。

其他同态加密还有混合乘法同态、减法同态、除法同态等，大体定义都差不多，这里就不一一介绍了。

目前加法同态加密已经应用到区块链项目中，而乘法同态由于存在算法设计、密钥存储等问题还难以落地。