【隐私计算笔谈】MPC系列专题（三）：不经意传输与混淆电路

不经意传输

不经意传输（Oblivious transfer，OT，也有翻译是茫然传输）是在构建安全多方计算时经常需要使用的一个模块。

在双方参与的不经意传输中，一方“Bob”输入一组数据，另一方“Alice”输入一个选择，从Bob输入的数据中选取一个。Alice只获得其所选择的数据，无法得知 Bob输入的其他数据。Bob无法知道Alice选择获得了哪个数据。如有一个2选1的不经意传输协议，Bob输入{𝑎₀,𝑎₁}，Alice输入𝑟∈{0,1} 计算结束后Alice获得𝑎_𝑟，但是无法获得𝑎_1-𝑟，Bob无法得知Alice输入的𝑟的值。若Alice输入的𝑟=0，则Alice获得𝑎₀，无法获得𝑎₁；若Alice输入的𝑟=1，则Alice获得𝑎₁，无法获得𝑎₀。Bob无法得知Alice具体获得的是𝑎₀还是𝑎₁。

不经意传输协议还有N选1，N选M等。将2选1不经意传输协议写作，N选1不经意传输协议写作。

将重复调用k次不经意传输协议写作，如Bob输入 ，Alice输入{𝑟1,𝑟2,…,𝑟𝑘},𝑟𝑖∈ {0,1},1≤𝑖≤𝑘，在协议计算结束后，Alice获得。

Naor-Pinkas不经意传输协议是经典的OT协议，其基于离散对数困难问题，通过三次公钥密码学操作实现了 。

Naor-Pinkas不经意传输协议中的公共参数有：𝑞阶有限域的𝑍𝑞、有限域𝑍𝑝、𝑍𝑝的生成元𝑔和𝑍𝑝的𝑞阶子群𝐺𝑞 。其中𝑝和𝑞的关系是𝑞|𝑝−1，即𝑝−1能够被𝑞除尽。

发送者输入两个长度为𝑙比特的数据(𝑥₀,𝑥₁)，接收者输入一个选择比特𝑟。

1. 发送者生成一个随机数𝐶，并将𝐶进行公开，接着发送者生成一个随机数𝑎，计算和。

2. 接收者生成一个随机数𝑘，1≤𝑘≤𝑞。再生成两个公钥𝑝𝑘_𝑟和𝑝𝑘_1-𝑟，𝑝𝑘_𝑟=，𝑝𝑘_1-𝑟=，接收者将𝑝𝑘₀发送给发送者。

3. 发送者计算。发送者对需要发送的数据(𝑥₀,𝑥₁)进行加密：

4. 接收者计算，然后计算𝑥_𝑟。

例：Alice 输入(𝑥₀=9,𝑥₁=5)，Bob输入选择比特𝑟=1。

1. Alice生成一个随机数𝐶=20，𝑎=11，计算，将C公开。

2. Bob收到C后，生成一个随机数k=10，在生成两个公钥𝑝𝑘₁=，𝑝𝑘₀=，Bob将𝑝𝑘₀=发送给Alice。

3. Alice收到𝑝𝑘₀后，计算 ，对需要发送的(𝑥₀=9,𝑥₁=5)进行加密，并计算其哈希值。

4. Bob收到𝐸0和𝐸1之后，计算由于Bob计算出了，因此Bob可以计算出𝑥₁： 

在第3步，Alice收到𝑝𝑘₀= ，基于离散对数困难假设，Alice无法求解出𝑘，也就无法得知Bob选择的r是1还是0。

在第4步，由于Bob只知道，基于离散对数困难假设，求解𝑎是困难的，因此Bob不知道𝑎的具体值，也就无得知，无法利用求解出𝑥0，只能求解出自己所选择的𝑥_𝑟=𝑥₁的值。若Bob选择了0，一样同理，Bob无法求解出𝑥₁，只能得知𝑥₀。

混淆电路（Garbled Circuit，又称杂交电路、加密电路）的思想起源于姚期智院士，之后Beave等人提出了混淆电路的定义。混淆电路的构造从门开始先加密一个门再延伸到加密整个电路。

对于布尔电路而言，电路实现与或非即可实现完备，可以模拟任意的函数。混淆电路是实现安全多方计算的另一种方式，通过对电路进行加密来掩盖电路的输入和电路的结构，以此来实现对各个参与者的隐私信息的保密，再通过电路计算来实现安全多方计算的目标函数的计算。

首先以与门为例，一个常见的与门及其真值表如下图所示，将该与门的输入线记为𝑤₁ , 𝑤₂，输出线记为𝑤₃。

随机生成 6 个密钥，分别表示𝑤₁,𝑤₂,𝑤₃这三条线为0和1时的两种情况。如分别代表𝑤₁为0和𝑤₁为1，分别代表𝑤₃为0和𝑤₃为1。接着该门利用对称加密算法En()生成4个密文，表示用𝑎, 𝑏作为加密秘钥，使用加密算法En()来加密𝑐，在对真值表进行加密后，形成一个新的输入输出表，该新表和该门的真值表呈现一一对应的关系：

将打乱顺序，在电路门储存这四个乱序的值，记为𝑐₁,𝑐₂,𝑐₃,𝑐₄将这四个值称为电路门的混淆值.假设门上两条线𝑤₁,𝑤₂的输入的值对为(0,1)，那么输入线对应的电路计算值为。输出导线𝑤₃对应的加密值有四个，分别为，由于对电路求值的一方不知道哪个才是真值.

所以使用对分别对进行解密，只有能够被成功解密得到，即为该门的输出值，对其它的值进行解密时会得到无效值。如何分辨有效值和无效值，可以在电路真值后面添加固定比特数的标志位，用来表明解密正确。如果是使用错误的秘钥进行解密，则无法得到正确的标志位，可以据此判断出是否是有效值。混淆电路的基础结构如下图所示,门𝑔可以是与门、或门等。 

若该门为整个电路的中间门，其输出是其他门的输入，那么将其输出继续作为输入重复以上操作就可。若该门为最后的输出门，其输出即为结果，那 么再将转换为0，若输出为则转换为1即可。

对于多个电路组成的门，当一个输入线分成多条分别接入到多个门，其分出的每条线上的信号标记都相同。对于一个门如有多个输出线，每条输出线的信号标记也都相同。如对于三个门组成的电路，分别令𝑤₁,𝑤₂,...,𝑤₇代表电路上的信号线，对于每一条信号线𝑤₁,𝑤₂,...,𝑤₇，分别生成独立的密钥，给定所有密钥后，通过上文所述的思路对真值表进行替换和打乱顺序，即使用个门的两个输入值对输出值进行加密，使用各个加密值替换真值表的相应位置，最后打乱真值表的顺序。 

混淆电路是安全多方计算中一个非常实用的工具，电路可以通过与或非门 实现任意一个函数，而多方计算的目标就是保护各方输入信息的情况下进行目 标函数的计算。通过目标函数的电路转换为混淆电路，可以实现保护隐私信息 的情况下进行目标函数的计算。

在双方计算的例子中，假设Alice为发送方，Bob为接收方。Alice设计一个混淆电路发送给Bob，由Bob负责进行计算。因为Bob不知道密钥和0、1的对应关系，因此 Bob无法得知电路的实际真值表。Alice直接将其秘密转换为密钥后发给Bob，Bob也不清楚其真值。Bob通过上文所述的不经意传输协议（OT）获得与其在目标函数的输入所对应的Alice的密钥，然后按照电路的结构逐个门进行计算，直到获得最后的函数计算结果。这样Bob 无法由于不知道Alice密钥和0、1的对应关系，因此无法得知Alice的实际输入。而电路计算过程都在Bob处完成，因此Alice也无法得知Bob的输入。这样既能实现双方合作进行目标函数的计算，也可以保护各方的输入隐私。