多方计算入门（科普）

本文旨在给出多方计算的技术概述，以及阐明背后的数学背景和工作原理。
多方计算基于满足以下条件的函数计算:
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 。

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