两富翁某地相遇，彼此看对方不顺眼，想要把对方比下去。对于单调且枯燥的有钱人而言，最直接的方式就是比比谁更有钱，但是出于隐私，俩人都不想让对方知道自己财富的具体数字，也不想像头图中石崇王恺比富那样无聊烧钱。如何在不借助第三方的情况下，让两人知道他们之间究竟谁更有钱呢？



这就是1982年姚期智博士（计算机领域最高奖图灵奖获得者）提出的著名的“百万富翁”问题，通过这个问题，他提出了多方计算（(Multiparty Computation, MPC）的概念，并成为了密码学的重要分支。



多方计算，联同同态加密、零知识证明等技术一起，在个人隐私要求越来越高、信息泄漏事件越来越多的当今环境中，将作为底层技术框架发挥巨大作用，最终推动信息安全保护措施的变革。



此外，我们都知道区块链的一个重要特征就是它是一个公开的数据库，所有链上的交易信息都公开可追溯，虽然这在一定程度上可以解决信息不对称和欺诈的问题，但也对交易隐私造成了很大的危害；虽然钱包地址是随机的，但本质上区块链是一个半匿名性质的数据库，通过闭包、关联分析等技术可以对账户画像，账户隐私、资产隐私也面临重大威胁。



基于此，本文将对上述技术的技术原理进行介绍，分析技术的应用场景，看看“富豪比富”的几种姿势，说不定，未来你我都用得上。

1、技术简介

本质上，多方计算、同态加密、零知识证明都是一种间接、迂回的方法，它们不直接使用关键信息，而是通过比较、计算、处理与关键信息对应的衍生信息，得到与比较、计算、处理关键信息同样的结果。

1.1 多方计算原理

下面将用两个例子，来讲一下多方计算不同实现方式的原理。

1.1.1 不经意传输

假设某旅行社拥有N个景点的旅游资料，我想去其中的A景点游玩，希望向旅行社购买相关资料做好出游功课。但是我非常在意自己的隐私，不希望向旅行社泄露自己的目的地是哪里。因此双方希望这笔交易能够满足以下隐私条件：



我不希望向旅行社泄露“我准备去A地”这一信息；

旅行社只希望出售我出钱购买的那份资料，而不泄露我未购买的其他资料；



乍看之下这种隐私条件似乎是无法满足的：旅行社只要把A地的资料给到我，就必然了解了“我正在关注A地”这一信息；除非旅行社把所有资料都给出，但是这又违背了旅行社的利益。



但是神奇的多方计算可以让交易在这种“不可能的条件”下达成。在多方计算协议中，旅行社把他拥有的N份资料使用某种双方协商同意的加密算法和参数进行加密，然后发送给我；我可以从密文中解密出A的资料，之后就无法再解密其他N-1份资料。



以下以N=2为例，基于Diffie-Hellman密钥交换协议，给出一种1 of 2 的多方计算实现方法的描述：



• 其中S（Sender）=旅行社，R（Receiver）=我，S拥有两份资料M0（假设是北京）、M1（假设是上海），我想去北京，所以想看资料M0：



这是多方计算的一种实现方式，不经意传输（Oblivious Transfer, OT），算法背后的原理是数学中的指数幂运算。实际操作时需要对我提供信息、旅行社提供资料的方式做设计，以避免追溯。

1.1.2 秘密共享

假设，你、小王和小李想知道三人的平均薪资，但又不想透露自己的具体薪资，那么要用什么方法达到这个目的呢？



如果有可信第三方，问题很容易解决。你、小王和小李有一个共同信任的老大哥，你们可以各自把自己的工资告诉大哥，大哥保证不泄漏任何一位的薪资，并计算出三人的平均薪资。最后，将平均薪资告诉大家。



但是在区块链这种不可信任网络中呢？在这种情况下，就能使用安全多方计算来解决问题了。简而言之，就是用算法代替可信第三方。





1. 你、小王和小李，各自选择一条抛物线，抛物线和Y轴的交点是自己的工资数。比如你的工资是100，你选择了一条抛物线y = 2x2+ x + 100。然后，在这条抛物线上取出3个点（1 , 103）、 （2, 110）、（3, 121）， 自己保留一个点（1 , 103），将另外两个点（2,110），（3, 121）信息分别加密传给小王和小李。同样的，小王将x=1的点加密传给你，x=2的点保留，x=3的点给小李；小李则把x=1的点加密传给你，x=2的点加密传给小王，x=3的点保留；

2. 至此，每个人都拥有了三个密码碎片（不同抛物线上的点）， 以你为例，你拥有（1,103），来自小王的（1, y2），小李的（1, y3），可以算出一个点（1, 103+y2+y3），小王可以算出一个点（2, ......），小李可以算出一个点（3, ......）；

3. 三人将各自算出的不同的三个点互通有无，这样每个人都有3个点，在此基础上，可以还原出一条抛物线（即一个二元二次方程），得到抛物线的截距，将截距除以3，得到的值就是三个人的薪资之和了。



这种方案下，三个人的薪资是保密的，因为，每个人只得到了对方抛物线的一个点，无法还原出对方的抛物线，因此无法算出截距，即使两人合谋掌握了2个点，仍然无法还原出另一个人的抛物线。



这是多方计算的另一种实现方式，秘密共享，算法背后的原理是数学中的方程运算。秘密共享是以适当的方式拆分秘密，拆分后的每一个份额由不同的参与者管理，单个参与者无法恢复秘密信息，只有若干个参与者一同协作才能恢复秘密消息。

1.2 同态加密原理

1.2.1 原理

同态加密（homomorphic encryption ，简称HE）是一种无须对加密数据进行解密，直接对加密数据进行处理的方法，如果数据库中的数据已经是加密存放的，则同态加密技术不会对加密后数据产生任何影响，存储、传输的过程中，都不需要还原加密数据。



同态加密的思想是在1978年提出来的，当时考虑的背景是，如果对加密数据（即密文）的操作是在不可信设备上进行的，我们希望这些设备并不知道数据的真实值（即明文），只发回给我们对密文操作后的结果，并且我们可以解密这些操作后的结果。



根据同态加密算法的不同，可以分以下几类：

• 如果满足 f(A)+f(B)=f(A+B)， 我们将这种加密函数叫做加法同态

• 如果满足 f(A)×f(B)=f(A×B)， 我们将这种加密函数叫做乘法同态。

• 如果一个加密函数只满足加法同态，就只能进行加减法运算；

• 如果一个加密函数只满足乘法同态，就只能进行乘除法运算;

• 如果一个加密函数同时满足加法同态和乘法同态，称为全同态加密，这也是最牛的。



现有算法中，RSA 算法对于乘法操作是同态的，Paillier 算法则是对加法同态的，Gentry算法则是全同态的（目前也只是方案设计层面，不算落地可用）。

1.2.2 举例

举一个简单的例子：

n个学生和1个老师通信，每个学生都有1个数据要发给老师，老师需要知道这n个数据之和，而学生们不想让老师知道每个数据的真实值。



采用同态加密的话，每个学生可以用加法同态加密函数将各自数据加密，再将这密文发给老师；老师只需要把n个密文相加，再将相加后的结果（即密文之和）解密，即可得到n个数据之和（即明文之和）。这样就保护了n个数据不被老师所知道，而且老师也得到了n个数据之和。



此外，很多地方都喜欢用下面这个例子来解释同态加密，虽然我觉得不太贴切，比如工人不应该能够看到金子，但能在很大程度上说明问题，特别能体现同态加密对数据处理过程中保护隐私信息的能力：



A买到了一大块金子，她想让工人把这块金子打造成一个项链，但是工人在打造的过程中有可能会偷金子，毕竟就是一克金子也值很多钱的说，因此他想到给金子装一个盒子的方法，让工人可以对金块进行加工，但是不能得到任何金子：

• A将金子锁在一个密闭的盒子里面，并且给这个盒子安装了一个手套，这个时候“金子”就变成了加密后的“金子+盒子”；

• 工人可以带着这个手套，对盒子内部的金子进行处理。但是盒子是锁着的，所以工人不仅拿不到金块，连处理过程中掉下的任何金子都拿不到，这个时候对“金子”的处理，其实是对“金子+盒子”的处理；

• 加工完成后，A拿回这个盒子，把锁打开，得到了项链。这个时候其实是对“项链+盒子”进行解密，拿到了“项链”。



1.3 零知识证明原理

零知识证明（Zero Knowledge Proof，ZKP）概念最早出现在1985年，后来成为密码学的研究课题，在这一技术下，验证者可以验证证明者的某个观点是真实的，且证明者无须提供、也不会泄露除了该观点是正确的之外的任何信息。



举个例子，四十大盗抓住了阿里巴巴，想让阿里巴巴带路，但是他不想泄漏自己的密码“芝麻开门”，于是他跟四十大盗商量：



我有一个办法，你们不需要知道咒语就可以确定我是知道开门密码的。这样，你们离我一箭之地，用弓箭指着我，你们举起右手我就念密码打开石门，举起左手我就念密码关上石门，如果我做不到或逃跑，你们就用弓箭射死我。



（待续）