最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

【全球时快讯】多方安全计算(3)MPC万能钥匙:混淆电路

来源:博客园

学习&转载文章:多方安全计算(3)MPC万能钥匙:混淆电路

前言

我们在讲解不经意传输(Oblivious Transfer,OT)的文章(安全多方计算(1):不经意传输协议)中提到,利用n选1的不经意传输可以解决百万富翁问题(两位富翁Alice和Bob在不泄露自己真实财富的情况下比对出谁更有钱),过程如图1所示,具体过程不再展开描述。


(相关资料图)

图1 基于n选1的OT协议实现百万富翁问题

图1中的例子虽然解决了两位富翁在不泄露财富时的比对问题,但是如果遇到其他计算问题(如财富求和)时怎么解决?是否有一种通用的方法,可以在不泄露Alice和Bob原始数据的前提下,实现各种计算问题?本篇文章将向您揭晓答案,即基于混淆电路的MPC通用场景计算

  • 重点在计算

混淆电路简介

我们在安全多方计算系列的首篇文章(安全多方计算之前世今生)中提到,基于混淆电路(Garbled Circuit,GC)可以实现MPC通用场景计算。

什么是混淆电路

混淆电路是双方进行安全计算的布尔电路。混淆电路将计算电路中的每个门都加密并打乱,确保加密计算的过程中不会对外泄露计算的原始数据和中间数据。双方根据各自的输入依次进行计算,解密方可得到最终的正确结果,但无法得到除了结果以外的其他信息,从而实现双方的安全计算。

混淆电路执行过程简述

以两方安全计算为例,假设参与方为Alice和Bob,则混淆电路执行过程分为四个步骤:

  • Step 1: Alice 将计算算法转为混淆电路

  • Step 2: Alice 和 Bob 进行通信

  • Step 3: Bob 解密收到的混淆电路

  • Step 4: 分享结果

每一步的执行细节,将在第三节中以经典的百万富翁问题为例进行详细介绍。

基于混淆电路实现安全两方数值比较

百万富翁问题可看作是安全两方的数值比较问题,本节将以数值比较计算方法为例,详述混淆电路执行过程中的四个步骤。

将数值比较算法转化为混淆电路

画出数值比较算法的逻辑电路

将可计算问题转化为混淆电路的前提,是得到数值比较算法的逻辑电路图

假设有两个正整数\(x,y\)。转换为二进制后,\(x,y\)可分别表示为:

其中\(x_i,y_i\in (0,1)\),当\(x>y\)时,\(x,y\)的比较过程可简化为:如果最高位\(x_n>y_n\),直接认定\(x>y\);否则,如果\(x_{n-1}…x_1>y_{n-1}…y_1\),认定\(x>y\),循环此过程直到最低位。

整个过程中,我们定义一个变量\(c_{i+1}\):

  • 即根据\(c_{i+1}\)就可以判断出\(x,y\)的大小。

不失一般性,可总结为\(c_{i+1}=1\)意味着:\((x_i>y_i)\)或($x_i=y_i $并且 \(c_i=1\))。这个总结等价于图2中的逻辑电路图:

同或(XNOR):相同为真,不同为假。

图2 \(c_{i+1}\)表达式的等价逻辑电路

则对于正整数\(x,y\)来说,将\(n\)个图中的逻辑电路进行串联,即可组成完整的数值比较逻辑电路,其中\(c_1=0\)。完整电路如图3所示。

图3 完整的正整数比较逻辑电路图

以最底层模块为例生成混淆电路

(1)写出逻辑电路的真值表

Alice画出可计算问题的逻辑电路后,接下来需要生成整个电路的真值表。我们以整个电路中最下面的模块为例,为了方便理解,我们为每个门电路的输出做上标记,如图4所示。

图4 为模块中的所有门电路输出做标记

图4中标记可理解为:输入为\(x_1\)和\(y_1\)的“同或门”的输出为\(f\);\(f\)与\(c_1\)是“与门”的输入,该门的输出为\(g\)等。图4中模块的门电路真值表如图5所示。

图5 将模块中每一个门电路表示为真值表

(2)以“同或门”为例将真值表转为混淆表

以图5中的“同或门”的真值表为例,讲解如何将真值表转为混淆表。真值表转为混淆表的过程可概括为3个步骤:

第1步:用随机字符串替换真值表中的0和1。

图中的“同或门”一共有3个标签(\(x_1、y_1、f\)),每一个标签有0或1这2个可能的值,因此我们需要用6个随机字符串,来代替3个标签的0\1,这一过程如图6所示。

  • 这里可以看到,每个值都是不一样的(随机值)

图6 用随机字符串替换真值表中的0和1

第2步:对替换字符串后的表做加密处理。

加密处理过程如图7所示,加密后的表有4行,每行仅有1个密文数据。图中每一个密文数据均经过两次对称加密而来,其中\(E_y(f)\)表示以\(y\)为密钥,对明文数据\(f\)进行对称加密

  • ⚠️留个疑问:只能用对称加密么?

图7 对替换字符串后的表做加密处理

第3步:将加密表的数据排序按行随机置乱

加密后的表有4行密文数据,如图8所示,将4行密文数据在加密表中所处的行随机置乱。

图8 对替换字符串后的表做加密处理

“将真值表转为混淆表”这一小节中的“字符串替换->加密->置乱”的过程,就是混淆电路的核心思想。

(3)以“同或门”为例对混淆电路进行解密

为了便于读者理解混淆电路的整个执行过程,先以前一小节的“同或门”混淆表为例,讲解另一参与方Bob如何对混淆电路进行解密。前一小节第3步中,Alice已完成了“同或门”混淆表的转换工作,\(x_1\)表示Alice的输入,\(y_1\)表示Bob的输入。混淆电路接下来的步骤如图9所示。

图9 Bob以“同或门”为例对混淆电路进行解密

此过程中,第4~6步展示的是Alice和Bob的通信过程。

第4步:Alice将“同或门”混淆表【加密表】发送给Bob。

第5步:Alice将自己真实输入所代表的字符串明文发送给Bob,Bob虽然拿到的是明文【与真值表对应的混淆值】,但是无法知道该明文字符串表示1还是0。

第6步:Alice与Bob利用不经意传输(OT)协议,将Bob真实输入所表示的两个字符串以密文【OT加密的】形式发送,Bob根据实际输入,正确解密【OT解密的】获得其中一条明文字符串。

Alice这边有\(k_{y_1}^1\)和\(k_{y_1}^0\)的加密值(OT加密的),Bob通过OT协议想获得\(k_{y_1}^1\)。

第7步:此时Bob已掌握两条明文字符串【即,\(k_{x_1}^0\)和\(k_{y_1}^1\)】。利用这两个明文字符串做密钥,分别尝试解密收到的“同或门”混淆表中的密文,其中仅有一条结果是正确的。

Bob如何知道哪条结果是正确的?

Alice对于“同或门”中\(f\)标签所表示的0\1明文字符串做加密处理时,可在明文前加128位的0。Bob强行解密完混淆表中的密文后,查看解密结果。如果解密出来的某个消息前面有128个0,就知道此条消息解密是正确的

最后一步:分享结果。Bob将混淆表中获得的正确消息【混淆的字符串】拿出,Alice拿出\(f\)标签所表示的0\1明文字符串映射关系。Alice和Bob即可共同知道“同或门”电路的执行结果。

⚠️:请注意,混淆电路实际执行过程中,Bob并不会将中间某个门电路的解密结果告诉Alice,仅将整个混淆电路的最终结果告诉Alice。

生成整个逻辑电路

在3.1.1小节画出数值比对算法的逻辑电路后,Alice列出整个逻辑电路中所有门电路真值表,对所有门电路真值表均按3.1.2小节中的“同或门”处理流程转换为混淆电路,Alice可得到整个数值比对算法的混淆电路。

Alice和Bob进行通信

① Alice将完整的混淆表发送给Bob。

② Alice将每个门电路中,需要用到的\(xi\),每个\(xi\)真实输入(0\1)对应的字符串发送给Bob。(实现Alice真实输入值的隐藏)。

③ Alice将每个门电路中,需要用到的\(yi\),每个\(yi\)所有可能输入(0\1)对应的字符串以OT协议形式发送给Bob。(OT协议实现Bob真实输入值的隐藏)。

Bob解密收到的混淆电路

① Bob利用获得的\(xi、yi、c1\),层层强行解密每个相关门电路的输出结果字符串(每个门只能正确解密一个字符串,不给Alice看,实现中间计算结果隐藏)。

② Bob最终可得到整个混淆电路的最终输出结果\(c_{n+1}\)所表示的字符串\(result\)。

Alice和Bob共享混淆电路处理结果

Bob将\(result\)给Alice看,Alice通过自己掌握的字符串对应表,看真实值0\1。如果为1,表示\(x>y\);否则,表示\(x≤y\)。

  • Alice最先知道比较结果

程序实现

参考:https://github.com/wbernoudy/pygarble

代码说明

功能:利用姚氏电路实现安全两方计算,Alice创建电路,Bob计算。

对于电路的构造,需要创建三个门电路数组:

  • 第一个:输入
  • 第二个:中间值
  • 第三个:输出

电路表示形式:[unique gate ID, type of gate, [input0, input1]]

  • 对于输入电路,[input0, input1]表示输入的序号

  • 对于其他电路,[input0, input1]表示其门的ID

Circuit类对象的创建参数:

  • 第一个参数是输入电路的个数
  • 其他参数是三个门电路
> from alice import *> on_input_gates = [[0, "AND", [0, 1]], >                [1, "XOR", [2, 3]], >                [2, "OR", [0,3]]]> mid_gates = [[3, "XOR", [0, 1]],>             [4, "OR", [1, 2]]]> output_gates = [[5, "OR", [3, 4]]]> mycirc = Circuit(4, on_input_gates, mid_gates, output_gates)

可以通过mycirc.poss_inputs实时查看电路的信息。

  • 每个密钥都是一对值,表示1或0的混淆后的字符串。
> mycirc.poss_inputs[{0: b"4diGEaU1jdM3Pu-BJNSP9g7_QPc4ujAzGxl2BGoVG0M=", 1: b"wIXEEaM1S004rNrGEJDCxjtkLItla98ybjKE70ffGRU="}, {0: b"GfwHUAuJvWac23NGyT8aeoJbUWAB-yBcucuQhUt2jwg=", 1: b"BfBToX-S0Jqxb5wA1nhFHga-QILPsYzRMRbmuVHgNa8="}, {0: b"louVKwBH3BVABygcEjSd_oZboJBUUFVSoS67q_YLu9E=", 1: b"W6Lk0qWa7ly0QqxOMIrkrQQP-EXBIkC2NHgUWPn2qY8="}, {0: b"_acYcuVdFNjgmHUhDsKe7rTJbg_o2-MSuBv1gBE_lp4=", 1: b"H27Eo04R8_6S9xAMYFo8sxzn_VmJITg9-joTa1HNTzI="}, {0: b"2ihLVa48z4b6c-xI7D7dWPVRMO-XyewKcVTegn2xDPY=", 1: b"u50GeBJpyRbmFLQnFETQmbTgan5vQLYSTtCEBhHQu98="}]

这时就可以在Alice一端使用这些密钥计算电路,例如输入为:0, 1, 0, 1:

> my_input = [x[y] for x, y in zip(mycirc.poss_inputs, [0, 1, 0, 1])]> my_input[b"4diGEaU1jdM3Pu-BJNSP9g7_QPc4ujAzGxl2BGoVG0M=", b"BfBToX-S0Jqxb5wA1nhFHga-QILPsYzRMRbmuVHgNa8=", b"louVKwBH3BVABygcEjSd_oZboJBUUFVSoS67q_YLu9E=", b"H27Eo04R8_6S9xAMYFo8sxzn_VmJITg9-joTa1HNTzI="]> mycirc.fire(my_input){5: b"\x01"}

可以看到,mycirc.fire返回的是一个字典,键对应的是输出门的ID(这里是5),(输出)值是编码后的一字节(这里为1)

然后将Circuit对象以字典的形式存储在json_data文件中。

然后Bob需要先加载json_data文件:

> from bob import *> mycirc = Circuit(json_data)

这时得到一个Circuit对象,里面只有计算后的结果,并没有包含所有情况,Bob只得到了最后计算结果。

> input = [b"4diGEaU1jdM3Pu-BJNSP9g7_QPc4ujAzGxl2BGoVG0M=", b"BfBToX-S0Jqxb5wA1nhFHga-QILPsYzRMRbmuVHgNa8=", b"louVKwBH3BVABygcEjSd_oZboJBUUFVSoS67q_YLu9E=", b"H27Eo04R8_6S9xAMYFo8sxzn_VmJITg9-joTa1HNTzI="]> mycirc.fire(input){5: b"\x01"}
  • OT

因为Bob并不想让Alice知道他的输入信息,所以这里需要只用OT技术,参考的是t-out-of-n OT:Non-Interactive t-out-of-n Oblivious Transfer Based on the RSA Cryptosystem

ot.py提供了两个类:AliceBob

> from ot import *> from alice import keypair # we will use this to generate some example keys> my_keypair = list(keypair().values())> my_keypair[b"tWiWGameWDMNOTUDRBM2FUWHkpPg9ZqWPM_e3bsvdqc=", b"5-x4_N0gwM_Hh0AYnSykYn2Ab4sCUw9iUzBVw9ZK8tw="]> alice = Alice(my_keypair)

Alice对象调用setup,开始OT,通常将结果(公钥和hash(消息)写入alice_setup.json文件中:

> alice.setup()Pubkey and hashes published.

创建一个Bob对象,参数为:Alice的消息个数,想要哪些消息,消息对应的ID,假设Bob想要获取Alice的第二个消息:

> from ot import *> bob = Bob(2, 1, [1])> bob.setup()Polynomial published.

默认情况下,Bob.setupalice_setup.json文件中读取数据,然后写入信息到 bob_setup.json文件。

> alice.transmit()G has been published.

待补充

总结

本文讲解了如何通过混淆电路解决百万富翁问题。实际上,计算机所能处理的所有可计算问题都可以转换为逻辑电路,这也就意味着,利用混淆电路可以解决所有的安全多方计算问题:即在混淆电路帮助下,凡是能被逻辑电路表示的计算方法,都能在保证参与方数据机密性的前提下得到正确结果。因此本篇文章将混淆电路称为解决MPC的万能钥匙

参考文献

[1] https://zhuanlan.zhihu.com/p/138371497

[2] https://zhuanlan.zhihu.com/p/138188677

[3] https://blog.csdn.net/qq_38798147/article/details/110727263

[4] https://blog.csdn.net/Matrix_element/article/details/117481369

关键词: 逻辑电路 百万富翁 万能钥匙