安全多方计算与混淆电路

安全多方计算的概念
- 安全多方计算的现实应用
“安全”的含义
- 半诚实安全性
混淆电路
- 混淆真值表
- 混淆电路
不经意传输
- 相关链接

本文整理了美国俄勒冈州立大学电子工程和计算机科学学院副教授Mike Rosulek关于安全多方计算与混淆电路的演讲主题的主要内容, 文中图片均来源于Mike Rosulek的演讲报告幻灯片, 请查看文末相关链接中Mike Rosulek的个人主页获取报告文件. 整理如有错误之处, 恳请批评指正, 谢谢!

安全多方计算的概念

安全多方计算是指互不信任的分布式参与方拥有各自的隐私输入, 他们试图在不泄漏各自输入的前提下, 共同计算某个函数, 并获得不超出函数计算结果的输出. 常见的安全多方计算场景有选举、拍卖等. 由于参与方之间是互不信任的, 因此在安全多方计算中通常需要保证如下性质:

隐私性(Privacy): 这是最重要的一点, 任何参与方不能获得任何所规定的输出之外的信息;
输入独立性(Input independence): 各个参与方必须独立选择自己的输入, 即不能根据其他参与方的输入来选择自身的输入;
输出一致性(Output consistency): 如果某个参与方获得了输出, 则所有参与方都将获得相同的输出.
...

上述性质在某些参与方是作弊或者共谋的情形下仍需保持.

安全多方计算的现实应用

2009年起的丹麦使用安全多方计算来计算市场均衡时甜菜的价格, 并保证菜农和购买方无法得到关于对方心理价位的信息, 这是安全多方计算在现实世界中的一次大规模应用, 其他例子, 还有广告输入、2017年波士顿工资平等研究等等.

“安全”的含义

如何理解“安全地”计算\(f\)的含义? 不妨列举一下安全性所需属性问题:

如果敌手获得的信息不只有\(f(x,y)\), 该怎么办?
如果敌手获得了\(f(x,y)\), 但阻止诚实参与方获得它, 该怎么办?
如果敌手迫使多个参与方的输出不一致, 该怎么办?
如果敌手选取的输入取决于诚实参与方的输入, 该怎么办?
...

实际上, 我们不会通过列表来定义安全性需要满足的属性. 我们需要给安全计算的安全性下一个定义, 即理想世界与现实世界范式(Ideal-Real world paradigm). 考虑两个参与方Alice和Bob, 分别拥有自己的隐私输入\(x\)和\(y\), 他们想计算\(f(x,y)\). 在理想世界中, 他们只需将各自的输入发给可信第三方(Trusted Third Party, TTP), TTP计算并返回\(f(x,y)\)给各参与方. 腐败参与方Bob在这个理想世界中: 可以选取任何输入\(y\)(但独立于输入\(x\)); 除了能获得\(f(x,y)\)的计算结果之外, 不能获得其他信息; 让诚实参与方Alice获得\(f(x,y)\), 而不是任何其他结果, 因为TTP只会发送正确的计算结果给诚实参与方. 因此, 理想世界非常简单, 敌手不能在其中做任何有害(harmful)的事情. 通过理想-现实范式(Ideal-Real paradigm)来定义多方计算的安全性, 其安全目标是现实协议交互与理想世界交互一样安全, 即任何对于真实协议的“攻击”, 都可以在理想世界中实现“相同的效果”. 我们知道在理想世界中唯一会发生的事情是harmless, 这意味着, 在现实世界中攻击协议会发生的事情也是harmless. 通常攻击的“效果”指的是敌手可获得或者计算出关于诚实参与方的信息或对诚实参与方输出造成某些影响. 这样, 我们可以给多方计算协议安全下一个定义:

对于任何现实世界的敌手\(\mathcal A\), 存在一个理想敌手\(\mathcal A’\), 使得诚实参与方输出与敌手输出(HonestOutput, AdvOutput)的联合分布不可区分.

不失一般性, 通常在理想世界中, 假设存在一个模拟器(Simulator)模拟敌手与现实世界交互. 模拟器有两个任务:

发送看起来像来自诚实参与方的协议信息;
通过检查敌手的协议信息来提取(extract)\(f\)的输入.

半诚实安全性

半诚实(Semi-honest, 或称为被动passive, 诚实但好奇honest-but-curious)敌手是一种特殊情况:

给定输入, 敌手会诚实地遵循协议;
敌手可能会基于他的视图尝试获取相关信息;
无提取(extract)步骤, 仅在给定理想输入和输出的情形下模拟序列(transcript).

2000年, Ran Canetti提出的通用可组合(Universally Composable, UC)框架, 详细介绍了协议的安全性证明, 相关内容读者可以参考Ran Canetti的这篇文章Universally Composable Security: A New Paradigm for Cryptographic Protocols, 这里不再做详细介绍.

混淆电路

混淆电路(Garbled circuit)协议, 是布尔电路的半诚实安全计算协议, 最早由姚期智教授在1986年提出. 在介绍该协议之前, 我们先简单介绍混淆真值表(Garbled truth table)的相关内容.

混淆真值表

假设拥有隐私输入\(x\)的Alice和拥有隐私输入\(y\)的Bob想共同计算某个函数\(f(x,y)\). Alice进行如下操作:

写出函数\(f\)的真值表\(f(x,y)\);
对每个可能的输入\((x,y)\), 选取随机密钥\((A_x,B_y)\);
使用相应的密钥加密每个输出: \(\mathbb E_{A_x,B_y}(f(x,y))\);
随机打乱密文的顺序, 并将所有密文发给Bob.

先假设Bob获得了正确的\(A_x,B_y\)(前者由Alice直接发送, 后者使用不经意传输Oblivious transfer, 这里暂不说明, 后面再补充), 通过试解密所有的密文, 只有一个密文\(\mathbb E_{A_x,B_y}(f(x,y))\)可以被成功解密, 即Bob只能得到\(f(x,y)\), 这就是两方所要计算的函数结果.

可以证明在仅仅给定Bob理想输入/输出的前提下, 模拟器可以模拟协议中Bob的视图(View).

上述混淆真值表方案有一个缺点: 开销与\(f\)的真值表大小成正比! 解决方案是与其加密函数的输出, 不如加密更多混淆真值表的密钥.

混淆电路

Alice和Bob想使用他们的隐私输入\(x,y\)共同计算函数\(f(x,y)\), 首先将函数\(f\)写成布尔电路的形式, 布尔电路的每个门(gate)拥有两条输入线路(wire)和一条输出电线, 输入线路分别对应于两个参与方隐私输入的单个比特, 且每个门都对应着一个真值表, 双方将使用该布尔电路来计算函数\(f\).

Alice作为电路混淆者(Garbler)生成并混淆整个电路: 为每条输入/输出线路选取两个随机标签\(W_0,W_1\), 分别代表线路真值0和1的标签, 为描述简单起见, 在下文中我们称输入线路上的标签为混淆输入(Garbled input), 输出线路上的标签为混淆输出(Garbled output); 使用每个门的混淆输入来加密门的真值表, 这样, 每个门都有4个密文; 将每个门的密文全部打乱后, 发送给Bob. 易见, 总的密文个数为门数的4倍. Bob作为电路评估者(Evaluator), 对于每个加密门, 使用从Alice处得到的混淆输入来解密该门对应的四个密文, 每个门只有一个密文可以被解密成功, 解密的结果为输出线路的标签值, 即混淆输出. 如下图所示. 注意到第三和第四个混淆表所对应的门是相同的, 但混淆表并不相同. 这是因为即使两个门类型相同, Alice也必须为其生成不同的混淆真值表而不能重用, 否则不同的混淆输入将泄漏混淆标签对应真值, 读者可以自行推理, 这里不做进一步探讨.

下面谈谈混淆电路的安全性. 主要思想是, 给定混淆电路和混淆输入, Bob只能盲目地(blindly)计算电路, 每条线路获得一个标签, 而难以猜测与之“互补”的那个标签. Bob所得到的单个标签隐藏了线路的逻辑真值, 由于标签是由Alice随机选取的, 因此Bob无法获知该标签与逻辑真值的对应关系. 最后Alice告诉Bob最终输出线路的标签与逻辑真值的对应关系即可得到电路的最终输出.

关于混淆电路的正式定义、具体混淆方案、安全性证明等相关信息, 读者可以参考2012年的这篇文章: Foundations of Garbled Circuits. 如下图所示, 正式安全属性主要考虑以下三点:

隐私性(Privacy): 混淆电路\(F\), 混淆输入\(X\)和解码信息\(d\)不会泄漏除函数\(f\)和\(f(x)\)之外的任何信息.

如果Alice发送所有门的混淆密文、部分混淆输入(上图中的\(A_1,B_0,C_0,D_1\))以及混淆输出(上图中的\(I_0,I_1\))给Bob, 则Bob确实可以得到输出\(f(x)\)(即上图中的\(I_0\)). 当试图隐藏布尔电路时, 实际上只需要隐藏门的混淆输入以及中间门的混淆输出, 但整个布尔电路是公开的, 因此会泄漏函数\(f\). 即除了\(f(x),f\)之外, \((F,X,d)\)没有泄漏其他更多信息.

不经意性(Obliviousness): 混淆电路\(F\)和混淆输入\(X\)不会泄漏除函数\(f\)之外的任何信息.
可靠性(Authenticity): 给定混淆电路\(F\)和混淆输入\(X\), 很难找到\(\tilde{Y}\)使得其解码后不属于集合\(\{f(x),\perp\}\).

如果Alice发送所有门的混淆密文、部分混淆输入(上图中的\(A_1,B_0,C_0,D_1\)), 则Bob可以得到其中一个混淆输出(上图中的\(I_0\)), 但如果Alice不告诉Bob另一个混淆输出(上图中的\(I_1\))是什么, 即不发送解码信息给Bob, 则Bob无法获得函数\(f(x)\)的具体输出. Bob很难找到解码后不属于集合\(\{f(x),\perp\}\)中的其他混淆输出\(\tilde{Y}\)来欺骗Alice.

还有一些其他有趣的概念, 了解其存在即可, 这里不做深究:

自适应安全性(Adaptive security): 输入的选取可取决于混淆电路;
门隐藏(Gate-hiding): 混淆电路\(F\), 混淆输入\(X\)和解码信息\(d\)不会泄漏除函数\(f\)的拓扑结构和\(f(x)\)之外的任何信息.

不经意传输

前面我们提到, 电路评估者Bob解密用的混淆输入分别是两方对应输入比特的标签, \(A_x\)可由Alice根据他的输入比特直接发送相应的混淆输入标签给Bob, 但是Bob如何获得他的输入比特\(y\)所对应的混淆输入标签呢? 注意到混淆电路是由Alice生成的, 因此只有Alice才知道混淆输入. 解决方案是两方需要运行一个不经意传输(Oblivious Transfer, OT)协议. Alice作为OT发送方, 取Bob输入线路的两个混淆输入\((W_0,W_1)\)作为OT的输入, Bob作为OT接收方, 将他在该线路上的隐私输入\(c\)作为OT的输入. 在协议结束后, Bob可以获得他在该线路上的混淆输入为\(W_c\), 但对\(W_{1-c}\)一无所知, 而Alice无法获知Bob得到了哪一个混淆输入(因为Alice并不知道Bob的隐私输入\(c\)).

那么如何构造不经意传输协议呢? 我们可以使用支持盲密钥生成(blind key generation)的公钥密码来构造. 具体步骤如下: OT接收者首先运行密钥生成算法\(\mathsf{KeyGen}\)生成一组公私钥对\((sk_c,pk_c)\), 然后使用\(\mathsf{BlindKeyGen}\)生成一个没有私钥的公钥\(pk_{1-c}\), 将两个公钥\((pk_0,pk_1)\)发送给OT发送者; OT发送者分别使用两个公钥加密两个混淆输入\(W_0,W_1\)得到两个密文\(\mathbb{E}_{pk_0}(W_0), \mathbb{E}_{pk_1}(W_1)\), 并将其发送给OT接收者; OT接收者使用私钥\(sk_c\)解密\(\mathbb{E}_{pk_c}(W_c)\)得到\(W_c\), 此即为混淆电路中Bob隐私输入所对应的混淆输入, OT发送者没有输出. 可以使用的公钥密码体制, 如ElGamal公钥密码体制, 其特点是选取群元素无需知道离散对数.

下面我们来概括一下混淆电路的步骤.

Alice将生成的混淆电路\(f\)的打乱后的密文, 他的混淆的输入\(x\)和输出线路的所有标签发给Bob;
对于Bob的每条输入线路, Bob与Alice运行不经意传输协议, 得到混淆的输入\(y\);
当Bob评估完混淆电路后, 通过输出线路的标签得到电路的计算结果\(f(x,y)\), 并将其发给Alice.

给定混淆电路\(f\), 混淆输入和所有的输出标签, Bob可以获得且只能获得电路输出\(f(x,y)\), Alice不能从OT协议中获得其他信息, 因此他只能获得Bob告诉他的电路输出结果\(f(x,y)\).