当前位置：首页 > news >正文

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

news 2026/1/19 13:05:57

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

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

起源

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

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

通俗的解

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

Alice准备9个箱子，分别给表面贴上1-9。
```
[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
```
Alice在箱子里放入苹果（P）和香蕉（X）。规则是：如果箱子序号小于x，放苹果，否则放入香蕉。
```
[1P]	[2P]	[3P]	[4X]	[5X]	[6X]	[7X]	[8X]	[9X]
```
把箱子封装后按照顺序交给Bob。此时Bob知道箱子序号（贴在外边），但是不知道里面放了什么果子。
Bob挑选序号数字和y相等的箱子[6X]，把序号撕掉[X]。
在Alice和Bob的共同见证下，他们打开了箱子。看看里面放的究竟是个什么玩意。

正经的解

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

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

Bob搞一个随机数 $r$ （用于封装箱子），计算 $m = E_{sb}(r)-y$ ，把 $m$ 发给Alice；
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个箱子）。
Alice拿一个素数 $p$ ， $p$ 的数量级比 $r$ 小。对 $B o x es$ 里的9个箱子（9个数）模 $p$ ，得到 $Boxes_p = [ D_{pb}(m+1) \mod p, D_{pb}(m+2) \mod p, ..., D_{pb}(m+9) \mod p ]$ 保留 $Boxes_p$ 的前 $x$ 项，对其他项+1（放入水果、撕掉标签）。得到
$Boxes_{pf} = [ D_{pb}(m+1) \mod p + 0, D_{pb}(m+2) \mod p+0, ..., D_{pb}(m+9) \mod p+1 ]$
Alice把 $Boxes_{pf}$ 按照序号发给Bob。此时，Bob会检查第 $y$ 个数，看它是不是等于 $\mod p$ （打开箱子看放的什么水果）。

为什么模 $p$ ?

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

安全多方计算的框架模型

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

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

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

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

在这里插入图片描述

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

通用型MPC：一般由混淆电路（GC）实现，具有完备性，理论上可支持任何计算任务。具体做法是将计算逻辑编译成电路，然后混淆执行，但对于复杂计算逻辑，混淆电路的效率会有不同程度的降低，与专用算法相比效率会有很大的差距。
专用型MPC：为解决特定问题所构造出的特殊MPC协议，由于是针对性构造并进行优化，专用算法的效率会比基于混淆电路的通用框架高很多，当前MPC专用算法包含四则运算，比较运算，矩阵运算，隐私集合求交集，隐私数据查询等。

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