Categories
程式開發

除了直接看余额,谁更有钱还能怎么比(一)


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

这就是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:

除了直接看余额,谁更有钱还能怎么比(一) 1

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

1.1.2 秘密共享

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

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

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

除了直接看余额,谁更有钱还能怎么比(一) 2

你、小王和小李,各自选择一条抛物线,抛物线和Y轴的交点是自己的工资数。比如你的工资是100,你选择了一条抛物线y = 2×2+ 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的点保留;至此,每个人都拥有了三个密码碎片(不同抛物线上的点), 以你为例,你拥有(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拿回这个盒子,把锁打开,得到了项链。这个时候其实是对“项链+盒子”进行解密,拿到了“项链”。

除了直接看余额,谁更有钱还能怎么比(一) 4

1.3 零知识证明原理

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

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

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

(待续)