安全多方计算系列笔记1——前世今生

这一系列笔记参考了绿盟科技研究通讯的安全多方计算文章，及其他。

首先看定义：在不泄露参与方原始输入数据的前提下，允许分布式参与方合作计算任意函数，输出准确的计算结果。

起源

安全多方计算问题及解首先由姚期智（1982）提出。

问题可以解释为：两个争强好胜的富翁Alice和Bob，各自有x和y百万（单位：刀）的财富，其中1<=x,y<10。如何在不露富的前提下比较谁更是富哥？

通俗的解

假定x=4,y=6。于是Alice有4M，Bob有6M。可以用如下的步骤进行财富的比较：

1. Alice准备9个箱子，分别给表面贴上1-9。

   [1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
   

2. Alice在箱子里放入苹果（P）和香蕉（X）。规则是：如果箱子序号小于x，放苹果，否则放入香蕉。

   [1P]	[2P]	[3P]	[4X]	[5X]	[6X]	[7X]	[8X]	[9X]
   

3. 把箱子封装后按照顺序交给Bob。此时Bob知道箱子序号（贴在外边），但是不知道里面放了什么果子。
4. Bob挑选序号数字和y相等的箱子[6X]，把序号撕掉[X]。
5. 在Alice和Bob的共同见证下，他们打开了箱子。看看里面放的究竟是个什么玩意。

正经的解

其实知道了这个大概流程，怎么用数学来描述解、用什么样的密码学工具（模、一次性密码本、不对称密钥etc）来实现就有很多方法了。

仍然假设x=4,y=6。Alice(a)和Bob(b)都有自己的公§、私(s)钥对（分别记为$pa,pb,sa,sb$），加密和解密的操作记为：$E_k(\cdot )$/$D_k(\cdot )$，其中k∈{pa,pb,sa,sb}k \in \{pa, pb, sa, sb\}k∈{pa,pb,sa,sb}。具体步骤为：

0. Bob搞一个随机数$r$（用于封装箱子），计算$m=E_{sb}(r)-y$，把$m$发给Alice；
1. Alice拿到$m$，因为不知道$r$是多少，所以猜不出$y$（一次性密码本的性质）。但是因为1<=x,y<10，所以Alice可以枚举y，于是他得到了$[m+1,...,m+9]$，进而得到$$Boxes=[D_{pb}(m+1),D_{pb}(m+2),...,D_{pb}(m+9)]$$（生成9个箱子）。
2. Alice拿一个素数$p$，$p$的数量级比$r$小。对$Boxes$里的9个箱子（9个数）模$p$，得到$$Boxe{s}_p=[D_{pb}(m+1)\mathrm{mod}p,D_{pb}(m+2)\mathrm{mod}p,...,D_{pb}(m+9)\mathrm{mod}p]$$ 保留$Boxe{s}_p$的前$x$项，对其他项+1（放入水果、撕掉标签）。得到
   $$Boxe{s}_{pf}=[D_{pb}(m+1)\mathrm{mod}p+0,D_{pb}(m+2)\mathrm{mod}p+0,...,D_{pb}(m+9)\mathrm{mod}p+1]$$
3. Alice把$Boxe{s}_{pf}$按照序号发给Bob。此时，Bob会检查第$y$个数，看它是不是等于$r\mathrm{mod}p$（打开箱子看放的什么水果）。

为什么模$p$?

读者不妨手写一下整个过程中Alice和Bob掌握的信息。如果不模个$p$，直接对$Boxes$中的项+0/+1的话，Bob在拿到$Boxes$之后就可以通过加密$Boxes$中的项并且和$m+1,...,m+9$进行比对，得到Alice的秘密$x$。

安全多方计算的框架模型

$n$个计算参与方分别持有各自的秘密数据
$$x_1,x_2,\dots ,x_n,$$
协议的目的是利用各方的秘密数据计算一个预先达成的共识函数
$$(y_1,y_2,...,y_n)=f(y_1,y_2,\dots ,y_n),$$
此时任意一方$i$可以得到对应的结果$y_i$，但无法获得其他任何信息，包括其他的$x$和$y$。

在传统分布式计算模型下，传统的分布式计算由中心节点协调各用户的计算进程，收集各参与方的明文输入信息，各参与方的原始数据对第三方来说毫无秘密可言，很容易造成数据泄露。

在MPC计算模式下，不需要可信第三方收集所有参与节点的原始明文数据，只需要各参与节点之间相互交换数据即可，而且交换的是处理后（如同态加密、秘密共享等处理方法）的数据，保证其他参与节点拿到数据后，也无法反推原始明文数据，确保了各参与方数据的私密性。

安全多方计算的技术体系架构

根据支持的计算任务，可以把安全多方计算分为两类：专用场景和通用场景。

• 通用型MPC：一般由混淆电路（GC）实现，具有完备性，理论上可支持任何计算任务。具体做法是将计算逻辑编译成电路，然后混淆执行，但对于复杂计算逻辑，混淆电路的效率会有不同程度的降低，与专用算法相比效率会有很大的差距。

• 专用型MPC：为解决特定问题所构造出的特殊MPC协议，由于是针对性构造并进行优化，专用算法的效率会比基于混淆电路的通用框架高很多，当前MPC专用算法包含四则运算，比较运算，矩阵运算，隐私集合求交集，隐私数据查询等。

虽然专用型MPC与通用型MPC相比效率更高，但同样存在一些缺点，如只能支持单一计算逻辑，场景无法通用；另外专用算法设计需要领域专家针对特定问题精心设计，设计成本高。