姚期智提出的"百万富翁"难题被破解?多方安全计算MPC到底是个什么鬼？

来源：区块链大本营作者：章磊

作者简介：章磊，ARPA联合创始人&首席科学家，美国乔治华盛顿大学金融工程硕士，拥有十年深度学习、AI算法和风险建模经验，并对密码学有深度钻研。曾于硅谷最大的股权众筹公司CircleUp担任资深数据科学家；此前其就职于世界银行、AIG、PineBridge等大型金融机构，精通人工智能和量化策略。同时章磊于2017年创立星尘数据，为AI行业提供数据赋能。

在越来越多对数据隐私的担忧声中，政府开始行动制定数据使用合规法案。而另一方面，对数据的保护，却产生了一个矛盾：大量的数据因为需要依法保护而无法被联合在一起计算。

反过来试想一下，如果全世界的基因数据能够联合在一起分析，人类或许可以更快找到癌症的解药。这让我们大胆地去思考，是否存在一种保护数据安全而又能够有效利用数据的方式？

1980年代，姚期智院士提出了「百万富翁」问题：两个百万富翁街头邂逅，他们都想炫一下富，比比谁更有钱，但是出于隐私，都不想让对方知道自己到底拥有多少财富，如何在不借助第三方的情况下，让他们知道他们之间谁更有钱？

在这个经典问题之下，诞生了「多方安全计算」(Multiparty Computation, MPC)这门密码学分支。MPC技术能够让数据在不泄露的情况下联合多方的数据进行联合计算并得到明文计算结果，最终实现数据的所有权和数据使用权的分离。

今天我们就来介绍一下MPC的出现背景和应用场景。在开始前，我们先来看看如今数据对于我们的意义。

01 我们正生活在数据保护的时代

个人隐私和数据隐私

2018 年 5 月 25 日正式生效的欧盟通用数据保护条例（GDPR）引起全球广泛关注，这部被称为「史上最严」的数据保护法案将对科技行业和个人生活产生深远影响，因为它是人类历史上第一个定义个人数据所有权的规则，它在法律上明确规定了个人数据是个人所有的数据资产。

这项法律将保障人们对个人数据有更多的掌控权。举例说明，社交网络公司在使用你的数据前必须征得你的同意。此项法律对创Facebook等科技巨头无疑影响很大，因为这些公司就指望着用户数据赚钱。

商业利益中的数据保护

数据是现代商业与个人的核心价值与重要资产。数据正在重新塑造人类生活的方方面面，包括金融、广告、零售、医疗、物流、能源和工业等。

随着人工智能时代的到来，数据在现代商业活动中也成为了最重要的竞争资源。巨头公司利用数据垄断的优势建筑起了行业壁垒。

例如，打车软件公司拥有人们每天出行的数据，包括乘客的起点与终点，他们可以利用这些数据来优化自己的产品和业务，甚至是用这些数据来进行一些预测，比如一个房地产价格指数或者一个政府道路优化方案。

数据的融合可提高其价值，数据的交叉使用可产生协同作用。但因为数据本身的可复制性和易传播性，一经分享无法追踪使用情况，数据资产的分享与协同开发受到严重制约。

既然如此，那数据保护的价值又从何说起呢？

02 被保护的数据如何产生价值?

虽然个人对隐私的保护、商业公司的数据保护，都是正当的利益诉求，但却产生了一个个数据孤岛。拥有数据源的中小型公司无法安全的将数据共享或变现。

对于数据使用者，大数据公司、开发者和科学家仅能接触到有限的数据集，并且费用高昂。与运营商等大数据源的合作需要开发人员现场部署模型于数据源的服务器上，模型算法存在泄露风险，且效率低下。

一方面，数据需要得到保护和隔离；另一方面，数据对人类社会的价值在于联合在一起的计算和分析。这是否是一个不可破解的矛盾？

理想情况下，我们可以委托一个安全可信的第三方对数据进行计算。然而，现实中，要么数据太重要而没有第三方，要么第三方会因为有了数据而拥有过多的权利，例如信用卡公司和电商公司，如果乙方能有对方的数据，会非常可怕。

要解决这个问题，就回到了本文最初提到的「多方安全计算技术」（MPC）。通过MPC，我们可以实现联合多方的隐私数据，在没有一个可信第三方的情况下，一起计算并得到分析的结果，而不担心各自的数据被泄露。

MPC是一套基于现代密码学的协议组，这个工具组里面有很多组件组成。

简单的来说，这套工具组里面有零知识证明（ZKP）、概率加密、信息理论消息认证码（MAC），各种分布式沟通协议和不经意的转移（OT），以及最重要的基础技术：秘密共享和秘密分片计算是实现安全多方计算的基础。

特别是，在被动对手的情况下，Shamir的多项式秘密共享是多方计算的基石，而Chor、Goldwasser、Micali和Awerbuch的可验证秘密共享在拜占庭对手问题中起着类似的作用。

在过去35年中，MPC算法和工程设计得到了实质性的改进，并且已经达到性能上不需要考虑协议性能视为使用的主要障碍的程度。

MPC社区采用了事实上的基准，即在两个参与者之间执行AES加密，一个带有加密消息，另一个带有密钥。 AES包含各种算术和布尔运算符，因此非常适合直接在硬件和MPC中进行计算。在过去十年中，安全计算提高了4-5个数量级。

出于比较目的和考虑摩尔定律的影响，下图显示了在相同时间段内本机AES计算的性能。

接下来，我们再来通过一个例子，更清晰的理解MPC的实现原理。请看下图：

根据上图所示，假设我们的目标是联合计算所有各方秘密数据的总和，这可以通过秘密共享来实现。

首先，每一方将其秘密号码随机分成三部分，并将其中两部分别分享给其他部分。

然后，每个方在本地对来自其他对等方及其自身的所有三个共享进为了公开最终结果，每个方的本地总和（local sum）都会公开给同行（Peers）。

最后，任何一方都可以通过将所有三个公共本地总和相加来知道最终结果。

秘密共享的关键点在于，通过了解秘密共享，一方不会获知有关私有数据的信息。例如，在通过揭示秘密共享5的三方计算中，秘密数据可以是10、79、-11这样的随机数字。即使知道秘密共享，该方也可以猜测私人数据，而不是猜测随机数。

由于在整个过程中没有显示隐私数据，因此秘密共享计算可以保护隐私。对手方不能发现秘密信息。

正式因为拥有这样的特性，MPC在现实世界中受到越来越多的重视，也被更多领域所采用。比如以下3类场景。

联合征信

MPC可赋能金融、保险企业对客户的负债率等风险指标进行联合分析。目前各家金融、保险、资产管理机构只掌握客户部分数据，从而导致风险评估误差。联合分析不泄露各参与方数据，对客户的风险有整体评估，在多头借贷等场景下能有效降低违约风险。

多维度健康分析

MPC赋能医疗机构对病人在多家医院的病历和智能硬件生物数据进行分析，从而在病人、医院和智能硬件厂商数据不泄露的情况下，对病人有更精准的诊断。同时，针对医疗机构的联合数据分析可以让药品研究机构对某特定地区特定病种有更全面的了解。

联合精准营销

MPC赋能商户对潜在客户多维度信息进行分析，从而更精准的投放广告。广告投放机构可以从更多数据维度对客户购买意向建模，且数据源不泄露个人隐私数据。

MPC与现实世界

以上是几个例子过于简单，现实世界的情况比这更复杂。

例如，用于添加的MPC是容易的，因为可以在秘密共享上本地计算加法操作。但是，乘法更加困难，因为如果没有其他工具帮助，它不能单独在本地共享上计算。不过利用同态加密（Somewhat Homomorphic Encryption, SHE），有更复杂的MPC协议可以实现安全的乘法。

好消息是任何函数都可以转换为加法和乘法的组合，因此基于秘密共享的MPC能够进行任何类型的通用计算，就像现代PC一样。

另一个例子是主动恶意节点（Actively Malicious）。主动恶意被定义为节点将偏离协议，与被动恶意相反，其中节点试图学习其他对等方秘密数据但始终遵循协议。

在上述秘密共享示例中，虽然没有节点可以学习其他私有数据，但是恶意节点可以发布错误的本地共享总和，从而使所有其他对等体学习错误的最终结果。

有各种方法可以发现这种恶意行为，甚至可以防止这种行为的发生。最流行的一种称为消息验证代码（MAC），其中每个操作都与一个数字相关联，以验证其正确性。一旦节点发出错误的消息，这个错误将很容易被其他节点验证。

而伪造一个能通过验证的错误数据的难度将是极其困难，这个难度非常大以至于造假的成本大于数据的收益。

03 MPC与其他实现技术的对比

除了MPC之外，还有一些能够实现类似功能的技术，包括同态加密、零知识证明、可信执行环境等。

但这些技术与MPC相比，都有一定的不足，我们一个个的来看看。

同态加密

同态加密（HE）是一种加密形式，允许对密文进行计算，生成加密结果，加密后的结果与操作结果相匹配，就好像它们是在明文上执行一样。

使用这样的工具，可以在不危及数据隐私的情况下外包存储和/或计算。因为HE允许在保持加密的同时计算加密数据，所以它已被广泛研究作为安全计算的候选者。

然而，即使最前沿同态加密方案仍然不能提供计有效运算深度算术电路。

首先，“bootstrapping”为已经非常繁重的过程增加了额外的成本。目前，HE的实际应用主要集中在评估函数的优化上，这通过限制电路倍增深度来避免昂贵的过程。

此外，根据该方案和目标安全级别，使用HE方案将导致巨大的密文扩展（从2,000到500,000甚至1,000,000倍的开销）。这是因为同态方案必须是概率性的，以确保语义安全性和特定的基础数学结构。正如我们所看到的，SHE方案在HE变体中是最有希望的，它将在我们后面提到的安全计算程序中使用。

零知识证明

零知识证明（ZKP）是一种这样的方法：一方（证明者Peggy）可以向另一方（验证者Victor）证明她知道值x，而不传达任何信息，除了她知道值x（读起来好绕口）。

最近很多的区块链项目在尝试利用ZKP作为可信的离线计算解决方案。在这些协议中，该运算模块被编译成电路并传输到第三方执行环境，在该环境中将使用该电路评估数据。

不过，与FHE方案类似，ZKP无法证明在远程环境中完成的实际工作量。除此之外，ZKP也无法保证计算是从恶意方的黑客手中获得的。

可信执行环境

可信执行环境（TEE）是一种在防分离内核上运行的防篡改处理环境。理想的TEE保证了执行代码的真实性、运行时状态、寄存器、内存和敏感I / O的完整性、以及存储在持久内存中的代码、数据和运行时状态的机密性。此外，它应能够提供远程证明，证明其对第三方的可信赖性。

硬件制造商渴望提出他们自己的可信硬件解决方案，但缺乏不同平台的通用标准。最杰出的工艺单元设计人员已将其硬件安全模块嵌入其产品中（例如英特尔软件保护扩展（SGX），ARM TrustZone，AMD安全加密虚拟化（SEV）和NVIDIA可信小内核（TLK）。

然而，最近的一些黑客攻击证明SGX还不能够承载协议级别的数据安全保护。事实上，这种看似安全的协议并不安全。

远程鉴权不会阻止一个恶意云服务提供商首先忠实地响应远程证明查询，然后在enclave外部模仿远程鉴定协议（例如KeyGen和CSR）。

换句话说，SGX不是为“通用组合”（Universal Composition）设计的协议，其中协议的真实行为和理想世界定义（功能）在计算上对于每个对手控制的环境都是无法区分的。简单来说，使用TEE，可以信任硬件，但不能信任控制硬件的人。因此，SGX最好用于许可网络，其中所有节点都经过预先批准，环境经过认证和信任。