本文旨在给出多方计算的技术概述,以及阐明背后的数学背景和工作原理。
多方计算基于满足以下条件的函数计算:
1)计算过程涉及多方(通常是机器);
2)每一方为计算提供一组输入,这个输入只有该方知晓;
3)进行计算时,在各方之间安全传递秘密信息,其过程不会泄露该方提供的任何信息;
4)计算结束后的函数输出和单方基于所有输入给出的结果无异;
5)计算在某种程度上是容错的,即使其中部分节点是恶意的,也不会影响计算继续并提供预期结果。

多方计算有很多实际用途,在云计算应用领域中,用户不信任云提供商将所有数据用于计算,
借此用户可以将数据拆分到多个云中并计算预期结果,无需信任单个云提供商持有用户的所有数据

下面是多方计算系统最简单的工作形式,它基于以下基础假设:
1)通过某种方式,各方发送消息的通信信道是安全的;
2)参与者遵循协议,除了协议指定的方式之外没有多余的交流;
3)参与者数量超过2个。

假设现在有一个包含 5 个人的列表,分别是 A1,A2,A3,A4和A5,目的是计算他们赚取的总薪水。
假设他们对应的薪水分别是 S1,S2,S3,S4,S5 , 那么需要计算的函数是$\sum s(i)$ ,每个人除了自己的薪水之外一无所知。

一个非常简单的解决方案是安排一个可信赖的中间人。
每个人都将他们的工资发送给中间人,而中间人计算总数并且向各方发布相同的内容。

但是很显然,多方计算的初心是剔除中间人的存在。
现在介绍一个无需中间人的解决方案:
假设先由A1启动协议,并创建一个随机数r,其中0≤r<M;
M是一个大数,满足 s1 + s2 + s3 + s4 + s5 <M。 因此,如果A1向A2发送包含(s1 + r)值的消息m1,那么A2 无法获知 s1 ,因此 A1 的输入值受到隐私保护。
现在由A2启动协议,与之前的过程类似,发送包含值(s2+r)值的消息m2,一直到A5向A1发送消息。

基于上述例子,阐述了一种简单的在不公开任何单独的输入 s1,….s5 的情况下计算预期结果的方法。

现在来介绍一个难度更高的例子——RSA解密。

RSA 算法的工作原理如下:

1)p和q是2个大素数,并且p * q = N ,N是公钥和私钥的模数;
2)计算函数 f(N)=(p-1) * (q-1);
3) 选择一个整数e,它满足范围区间(1,f(N)) ,使得 e 和 f(N) 互质;
4)将值对(e,N)以公钥的形式发布出去;
5)计算值 d ,使其满足 d * e=1+k * f(N),其中 k 为正整数。
6)保存好私钥(d,N)
RSA 解密操作的定义是 {Cipher}^d mod N;
基于多方计算,最简单的方法是将私钥拆分成多个部分,
很容易联想到,由此 d=d1+d2;
可得 ${Cipher}^d$ 即 ${Cipher}^{(d1+d2)}$ = $[{Cipher}^{d1}]$*$[{Cipher}^{d2}]$ ,并且注意
ab mod N = [(a mod N)(b mod N)] mod N 。

本文并没有介绍保护整个计算的措施,会在以后的文章中提到,期待再见~

Leave a Reply

Your email address will not be published.

当前无网络链接