一起聊聊安全多方计算

安全多方计算（ Secure Multi-party Computation, MPC 或 SMPC ）源于 1982 年姚期智院士提出的百万富翁问题，主要研究针对无可信第三方情况下，安全地进行多方协同的计算问题。即在一个分布式网络中，多个参与方协同计算一个约定函数，除计算结果以外，各参与方无法通过计算过程中的交互数据推断出其他参与方的原始数据。

安全多方计算不是一种单一的技术，它是由一系列技术组成的集合。安全多方计算的基础技术包括秘密共享（Secret Sharing，SS）、不经意传输（Oblivious Transfer，OT）、混淆电路（Garbled Circuit，GC）、同态加密（Homomorphic Encryption,HE）等。

秘密共享作为现代密码学的重要分支，不仅是保护数据安全的重要手段，也是安全多方计算的基础应用技术之一。

秘密共享通过将秘密信息分割成若干秘密份额并分发给多人管控，以此来达到风险分散和容忍入侵的目的。

一般来说，一个秘密共享方案由一个秘密分割算法和一个秘密重组算法构成，包含秘密分发者、秘密份额持有者还有接收者三类角色^[1] 。秘密分发者持有秘密信息并且负责执行秘密分割算法，并将秘密份额分发给秘密份额持有者。接收者是试图重组秘密信息的一方。当接收者希望重组秘密信息时，将从一组授权的秘密份额持有者中收集秘密份额，并执行秘密重组算法计算秘密信息，当有充足的秘密份额就可以重新恢复出秘密信息。一个参与方可以同时承担多个角色。

图 1 基于秘密共享的安全多方计算

基于秘密共享的安全多方计算原理如图1所示。参与方A和B分别拥有秘密值x和y，需要计算z=f(x,y),但不希望泄露秘密值给对方。A和B分别对秘密值使用秘密分割算法，获取份额(x₁,x₂...x_n)和(y₁,y₂...y_n)，将份额发送给节点s₁,s₂...s_n。节点s_i计算z_i=f(x_i,y_i)。获取足够的z_i，执行秘密重组算法，即可获取z。

不经意传输是安全多方计算的重要基石，最初由Rabin于1981年提出^[2]。如图2所示，该协议中发送方Alice拥有两个秘密消息和，接收者Bob只能选择接收其中的一个秘密消息，但无法得到关于的任何消息，Alice无法知晓接收方选择的是哪一个消息。

图 2 不经意传输

现有的OT协议只能用公钥密码系统来实现，公钥密码系统相对对称密码系统性能较低，无法适用于大规模数据传输的场景。为了解决该问题，研究者提出了OT Extension协议。在OT Extension中，Alice和Bob先执行少量的普通OT协议来传送较短的密钥种子。然后运行扩展（Extension）协议，通过对称密码算法把普通OT阶段的结果延长。这种设计思想类似于信封加密系统中先用公钥传输对称密钥，再用对称密钥加密传输大文件。

混淆电路由姚期智于1986年提出，是针对半诚实敌手模型的两方安全计算协议^[3]，其核心思想是将任何函数的计算问题转化为由“与”门、“或”门和“非”门组成的布尔逻辑电路，再利用加密技术构建加密版本的布尔逻辑电路。混淆电路包含布尔逻辑电路构建和布尔逻辑电路计算两部分。

下面以“与”门（AND门）为例简单说明姚氏混淆电路的主要思想，见图3。复杂电路就是将一个个门电路组合起来。假设Alice的秘密输入比特为a，Bob的秘密输入比特为b，计算AND门，即c=a&b，分为电路构建和电路计算两部分。

图 3 AND门混淆电路

电路构建：Alice给每个电线随机选择两个密钥： ，，其中对应 Alice的输入a=0，其他符号类似。Alice构造加密真值表，并随机打乱顺序获得混淆的加密真值表。Alice将混淆的加密真值表发送给Bob。

电路计算：Alice 将发送给 Bob，Bob通过不经意传输协议获得。Bob 使用和对混淆的加密真值表进行解密得到。Bob将发送给Alice。如果，那么输出结果a&b=0；如果，那么输出结果a&b=1。Alice将结果分享给Bob。

同态密码的概念最初是由Rivest等人于1978年提出。同态加密是基于数学难题的计算复杂性理论的密码学技术。对经过同态加密的数据进行处理得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的。本质上，同态加密是指这样一种加密函数，对明文进行环上的加法和乘法运算再加密，与加密后对密文进行相应的运算，结果是等价的。

同态加密分为三种类型：部分同态加密（Partial homomorphic encryption,PHE）、浅同态加密（Somewhat homomorphic encryption,SHE）和全同态加密（Fully homomorphic encryption,FHE）。

部分同态加密仅支持单一类型的密文域同态运算：常见加法同态（Additively homomorphic encryption,AHE）或乘法同态（Multiplicative homomorphic encryption）；浅同态能够支持密文域有限次数的加法和乘法同态运算；全同态能实现任意次的加法和乘法同态运算。

安全多方计算提供输入秘密数据的隐私保护能力，实现隐私保护计算过程的安全。目前安全多方计算主要有两条实施技术路线，包括通用安全多方计算和特定问题安全多方计算。前者可以解决各类计算问题，但是开销较大；后者针对特定问题设计专用协议，如隐私集合求交PSI（Private Set Intersection，PSI），隐私信息检索（Privacy Preserving Information Retrieval，PIR）等，计算效率较高，但是需要针对特定场景进行设计。

通用安全多方计算解决方案主要包括基于秘密共享的安全多方计算解决方案、基于混淆电路的安全多方计算解决方案以及基于全同态加密的安全多方计算解决方案。全同态加密目前仍处理理论研究阶段，距离实际应用尚远。目前在各领域中应用较为广泛的是基于秘密共享和基于混淆电路的安全多方计算方案。

基于秘密共享的方案：采用基于秘密共享的方式实现各类通用计算，中间计算值以秘密份额的方式存在。在此基础上进行应用层算法的指令改写，构造安全多方计算的电路实现秘密份额上的基本运算，如加法、乘法、比较等。基于秘密共享方法的SMPC协议通信轮数与电路的深度成线性关系，所以在相同的计算需求背景下，通信轮数更多。

基于混淆电路的方案：其通信轮数与电路深度无关，因此在机器学习训练等较深的电路需求背景下，总通信轮数更少，但总通信量更大。

针对特定问题的安全多方计算解决方案，主要包括隐私集合求交集（Private Set Intersection，PSI）、隐私信息检索（Privacy Preserving Information Retrieval，PIR）、安全多方统计（Privacy Preserving Statistical Analysis，PPSA）、保护隐私的数据挖掘（Privacy Preserving Data Mining，PPDM）等。下面介绍一下比较有代表性的PSI。

隐私集合求交集PSI：PSI指通过一系列底层的密码学技术，允许参与方使用各自的数据集合计算交集，且不会泄露交集以外的任何数据，在黑名单共享、营销匹配等现实场景中有广泛应用。

近些年PSI技术在理论和工程实现上均得到迅猛发展，一些PSI协议可以达到上亿量级的数据处理能力。

根据底层所用技术的不同，PSI可以分为基于公钥加密机制的PSI、基于电路的PSI和基于不经意传输协议的PSI三类。

一般地，基于公钥加密机制的PSI通信复杂度和计算复杂度都与集合大小成线性关系，虽然通信复杂度在几类PSI中最低，但是计算开销随着集合增大变得非常高。

由于计算交集的整个逻辑（或算术）电路的门数和深度很大，基于电路的PSI计算效率很低。

随着OT协议的快速发展，基于OT协议的PSI在时间复杂度和通信复杂度均得到很大提升，特别适用于大规模数据交集计算。

目前，基于公钥加密机制的PSI由于其原理的简洁性，在工业中的应用较为广泛。