可复用Garbling 的注解*

胡予濮，董思越，王保仓，刘 君

西安电子科技大学 综合业务网理论与关键技术国家重点实验室，西安710071

1 前言

Garbling 是一个有着多重应用的密码原语.Garbling 主要适用于权力受限的场景，其中最早的应用是安全多方计算(MPC)[1，2].随后出现的应用有属性加密(ABE)和函数加密(FE)，有意思的是garbling和FE 常常互为底层结构[3，4].Garbling 还被应用于不可区分混淆(indistinguishability obfuscation，IO)[5-7].注意到garbling 和obfuscation 的中文翻译同为“混淆”，说明garbling 和IO 有相似的功能，但后者的定义更强大.

1.1 Garbling 的两个基本场景

Garbling 的所有应用都源于以下两个基本场景，是这两个基本场景的组合或变形.

关于上述两个基本场景，我们有以下三个注解.

注解1 基本场景一中的“定向选择不经意传输” 是容易实现的.

注解2 基本场景一就是多方安全计算的底层结构.以用户U1和用户U2的两方安全计算为例，设用户U1知道x1，用户U2知道x2，双方都知道电路C(·，·).双方希望共同计算C(x1，x2) 的值，但U1需要隐藏x1，U2需要隐藏x2.于是，首先取f(·)C(x1，·)，U1和U2在基本场景一中分别扮演Alice 和Bob，使U2获得f(x2)C(x1，x2).其次取f(·)C(·，x2)，U1和U2位置互换，在基本场景一中分别扮演Bob 和Alice，使U1获得f(x1)C(x1，x2).两次使用基本场景一，就使用户U1和用户U2都得到C(x1，x2)(正确性);但U1不知道x2，U2不知道x1(隐私性).

注解3 基本场景二不能成为多方安全计算的底层结构.这是因为在基本场景二中，一方拥有的知识包含了另一方拥有的知识，不符合多方安全计算的场景设置.

1.2 可复用garbling 及我们以往的工作

2013 年以前的garbling 方案[1，2，8，9]都是一次性garbling.即一次编码(基本场景一或基本场景二)只能计算一个f和一个x的组合值f(x)，否则将不能保证隐私性.Goldwasser 等人[3]和Agrawal[4]提出了可复用garbling 方案.从字面意思来理解，可复用garbling 似乎满足以下标准: 一次编码能计算一个f和任意多个x的组合值f(x)，同时保证隐私性(如果是这样的话，可复用garbling 就是IO 了).然而我们[10]对可复用garbling 的有效性进行了分析，指出它只达到了一个更弱的标准: 对f的一次编码确实可以用来计算多个x的组合值f(x)，但对变量(值或域) 的一次编码只能计算一个x的组合值f(x).这就是说，可复用garbling 实际上仍然是一个一次性garbling.

1.3 本文的工作

本文继续讨论可复用garbling 的可用性和效率.本文指出以下两点: (1) 即使可复用garbling 被当作一次性garbling 使用，也常常是不可用的，它只能用于两个基本场景中的基本场景二，不能用于基本场景一.结合本文前述的注解3 可知，可复用garbling 至少不能用于安全多方计算(MPC).(2) 即使可复用garbling 被当作一次性garbling 用于基本场景二，没有证据表明它比原来的一次性garbling 效率更高.本文工作的细节如下.为了说明第(1) 点，本文首先指出对变量的编码并不是与f相互独立的，而是要用到f的信息.换句话说，对变量的编码可以看作对f的编码的另一部分.在此基础上，本文说明在可复用garbling 方案中，要么Alice 的知识包含Bob 的知识，要么Bob 的知识包含Alice 的知识，因此不符合基本场景一的场景设置.为了说明第(2) 点，我们仔细讨论可复用garbling 的中层结构和底层结构(由于我们[11]已经指出Agrawal 的中层结构/底层结构[4]不可用，因此只能讨论Goldwasser 等人的中层结构/底层结构[3]).在此基础上，我们将可复用garbling 方案与一个以前的一次性garbling 方案[9]进行比较.我们说明，当前者不使用全同态加密技术中的自举(Bootstrapping) 和降模(Modular switching) 运算时，前者的计算复杂度远远高于后者的计算复杂度;当前者使用自举或降模运算时，两者的比较非常复杂，但没有迹象显示前者的计算复杂度更低.

2 BHR12: 主流的一次性garbling 方案

2.1 布尔电路的一般表达式

布尔函数的一般表达式是按照运算顺序来表示每一步的{两个输入比特，运算符号，一个输出比特}.设运算符号集为{+，×}，其中‘‘+” 为比特异或，‘‘×” 为比特与，则n维布尔函数f(x) 的一般表达式如下.

· 输入:x(x1，x2，···，xn)，xn+1.其中xn+11 为常数.

· 对于in+2，n+3，···，N，令xi ←xa(i)Oixb(i).其中a(i)1，2，···，i-1}，b(i)1，2，···，i-1}，a(i)＜b(i)，Oi {+，×}.

· 输出:xN.其中xNf(x).

我们称{(x1，x2，···，xn)，xn+1;(xi，a(i)，b(i)，Oi)，in+2，n+3，···，N}为n维布尔函数f(x) 的一般表达式，称N为f(x) 的电路尺寸，称{(a(i)，b(i))，in+2，n+3，···，N}为f(x) 的电路拓扑结构，称{Oi，in+2，n+3，···，N}为f(x) 的电路运算符号序列.

2.2 BHR12 garbling 方案的基本场景一[9]

取两个公开的概率分布X0和X1，这两个概率分布能够完全区分.取一个公开的对称加密算法E(·，·)，其中的两个位置依次为明文位置和密钥位置.

2.2.1 编码(Alice)

第一步(随机设定): 对于每个i1，2，···，N-1，随机选取一个0，1}，然后定义Xi，0Xj，Xi，1X1-jmod 2.对于iN，定义Xi，0X0，Xi，1X1.

2.2.2 传输(Alice→Bob)

2.2.3 计算(Bob)

2.3 BHR12 garbling 方案的基本场景二[9]

基本场景二与基本场景一的唯一区别是，Alice 不是将变量域编码用“定向选择不经意传输” 的方式发给Bob，而是直接根据x的值对进行选择，然后将选择的结果发给Bob.这就是说，Alice 的知识是{x，f}，Bob 的知识仅仅是f(x).

3 可复用garbling 方案[3，4]

本节回顾可复用garbling 方案，我们将分为高层结构、中层结构、底层结构来叙述该方案.

3.1 高层结构: 可复用garbling=函数加密+对称加密

使用一个对称加密算法E(·，·)，其中的两个位置依次为明文位置和密钥位置，对应的解密算法为D(·，·).使用一个公钥函数加密算法E′(·，·)，其中的两个位置依次为明文位置和主公钥位置;当主私钥为K、函数为g时，对应的解密钥记为S(K，g)，解密得到明文m的函数值g(m);对应的解密算法为D′(·，·).高层结构分为以下的编码、传输、计算三部分.

3.1.1 编码

(1) 对于函数f，取定对称密钥k0，计算f*E(f，k0).即将电路f表示成一个比特串，用对称密钥k0加密.

(2) 取f**(x，k)(D(f*，k))(x).即f**(x，k) 为如下电路: 先计算比特串FD(f*，k)，再将此比特串F作为电路作用于输入值x，得到输出值F(x).(容易看出，当kk0时f**(x，k)f**(x，k0)f(x)，当k为其他值时f**(x，k) 与f(x) 无关)

(3) 生成公钥函数加密的主公钥和主私钥{mpk，msk}，并计算对应msk 和函数f**的解密钥S(msk，f**).记SS(msk，f**).

(4) (电路f的编码) 记(f*，S)，就是原电路f的编码.这个可以在多个x计算f(x) 时重复使用，因此被称为可复用garbling 的电路编码.

(5) (变量域或变量值的编码) 对任意x，计算E′((x，k0)，mpk)，就是变量值x的编码.

3.1.2 传输

3.1.3 计算

3.2 中层结构: 函数加密=属性加密+全同态加密+一次性garbling [3]

Goldwasser 等人[3]和Agrawal[4]各自为可复用garbling 的高层结构设计了函数加密方案.由于我们[11]已经指出，Agrawal 的函数加密方案[4]是无效的，因此只回顾Goldwasser 等人的函数加密方案[3].该方案的结构是属性加密+全同态加密+一次性garbling.其中的属性加密方案不是原始的ABE，而是扩展版的ABE2.具体来说，ABE2的解密者并不是只有当手中的函数值为1 时才能正确解密，而是: 当手中的函数值为1 时能解密一半;当手中的函数值为0 时能解密另一半.将原始的ABE 扩展为ABE2是容易的.

在函数加密的密钥生成阶段，顺序做以下六步操作.

(1) 构造一个全同态加密方案.其中的{全同态加密密钥，对应的解密密钥} 作为每次加密时的可变参数.

(2) 取3.1.1 小节中的布尔函数f**，构造f**关于全同态密文的同态函数f***.请注意f***是全同态密文的函数.

(3) 将f***表示为分量布尔函数的形式:f***其中每个都是全同态密文的布尔函数，λ为分量布尔函数的个数(我们知道λ「log2，其中q是全同态加密方案中所使用的模).

(4) 构造λ个ABE2方案，分别记为ABE2，1，ABE2，2，···，ABE2，λ.这些方案的属性加密密钥作为固定参数，共同成为3.1.1 小节中的K0.

(5) 对于每个ABE2，i，i1，2，···，λ，生成布尔函数对应的解密密钥ki.具体地说，ki的作用如下.设ABE2，i的密文是明文{p0，p1}的对应密文，密文后面还附有一个公开的标签label.则当(label)1 时，ki只能解密得到p1;当(label)0 时，ki只能解密得到p0.

(6){(，ki)，i1，2，···，λ}作为固定参数，成为3.1.1 小节中的S(msk，f**).在函数加密的加密阶段，顺序做以下六步操作:

(1) 取3.1.1 小节中的(x，k0) 为明文.

(2) 临时选取全同态加密方案的{全同态加密密钥，对应的解密密钥}，对(x，k0) 做全同态加密，得到全同态密文ψ.ψ将作为所有属性加密密文后附的标签.

3.3 底层结构: 一次性garbling=BHR12 garbling 方案[9]

BHR12 garbling 方案完全适合用于中层结构里的一次性garbling，因为BHR12 方案对电路类型基本上没有限制，只要多项式时间可计算.而其他一些一次性garbling 方案(如文献[8]) 限制电路为常数深度.BHR12 方案的另一个优势是不需特殊的密码工具，只需要对称加密算法.而其他一些一次性garbling方案则使用分支程序或随机化矩阵等特殊工具.

3.4 我们对可复用garbling 的已有分析结果[10]

我们曾指出，可复用garbling 没有达到“一次编码多次计算”，只能达到“对电路的一次编码可以用于多次计算”，而对变量域或变量值的一次编码只能用于一次计算.这就是说，可复用garbling 实际上仍然是一个一次性garbling.

4 可复用garbling 的可用性分析

本文继续讨论可复用garbling 的可用性和效率，只不过将其当作一次性garbling 来使用.本节讨论的问题是: 它能否用于第1 节中描述的基本场景一.

4.1 在基本场景一中的可用性

首先，对变量值x的编码不仅要知道x，还要知道k0，而k0是f的信息的一部分:E(f，k0)f*，fD(f*，k0).换句话说，对x的编码可以看作是对f的编码的另一部分，即对f的完整编码不是而是

其次，我们关注高层结构.总设Alice 做电路f的编码，于是Alice 知道电路f.

如果Alice 做变量域或变量值的编码，则她必须知道变量值x.于是Alice 的知识是{x，f}，Bob 的知识仅仅是f(x).

如果Bob 做变量域或变量值的编码，则他不但要知道x，也要知道k0.另外，Bob 肯定知道f*(因为f*是的一部分)，而且由{f*，k0}立刻得到f:fD(f*，k0).于是Alice 的知识为f，Bob 的知识为{x，f}.

综上所述，无论是Alice 还是Bob 做变量编码，一方的知识总是包含另一方的知识，不符合基本场景一的知识分布.因此，即使可复用garbling 被当作一次性garbling 使用，它至少不能用于安全多方计算.

4.2 关于一种补救方法的说明

Goldwasser 等人[12]提出了“多输入函数加密” 方案.如果用这个方案替代高层结构中的函数加密方案，则不但能使可复用 garbling 用于基本场景一，而且能获得更强的可复用性，即 IO.具体地说，利用多输出函数加密方案的 “分散加密集中解密” 特点，在函数加密的加密阶段 (3.1.1 小节第 (5) 步)，{E′(x，mpk)，E′(k0，mpk)}，而不是xE′((x，k0)，mpk);在函数加密的解密阶段(3.1.3 小节)，将E′(x，mpk) 和E′(k0，mpk) 两个密文集中在一起进行解密，得D′(，S)D′((E′(x，mpk)，E′(k0，mpk))，S)f(x).做了这样的改变之后，把E′(x，mpk) 的计算交给Bob，把E′(k0，mpk) 的计算交给Alice.于是Alice 提交的所有内容都是可复用的，Bob 可以任意多次计算而不必每次都与Alice 交互.

然而，这个“多输入函数加密” 方案的底层结构都是IO.我们知道，IO 如果存在，其本身就是强大的可复用garbling，根本不用再构造成另一个体制.可复用garbling 的构造避免使用IO，就是为了避免巨大的尺寸和难以清晰的安全性.

5 可复用garbling 的效率分析

本节将可复用garbling 当作一次性garbling，用于基本场景二(见第1 节)，将其与BHR12 方案[9]进行比较.设变量x的长度为n，f作为比特串的长度为n′，f作为布尔函数的尺寸为N.设可复用garbling 方案和BHR12 方案使用的对称加密方案相同，都是E(·，·) 和D(·，·).设E(·，·) 的电路尺寸为N′(注意到E(·，·) 是多输出布尔电路，从单输出布尔电路的尺寸推广到多输出布尔电路的尺寸是容易的).根据对称加密体制的现状，D(·，·) 的电路尺寸应该稍大于N′.设可复用garbling 方案中使用的属性加密体制的个数为λ，我们知道λ「log2，q为全同态加密方案的模.

5.1 BHR12 garbling 方案的计算复杂度

BHR12 方案在编码阶段的主要计算是4(N-n-1) 个对称加密.在编码阶段的其他计算为2N-1次抽样和(N-n-1) 次随机排序，其中每次随机排序是对四个数字的排序.

BHR12 方案在计算阶段的计算是4(N-n-1) 个对称解密，其中的N-n-1 个对称解密为解密成功，另外3(N-n-1) 个解密为解密失败.

5.2 我们的两个观察

第一个观察: 当可复用garbling 方案不使用全同态加密技术中的自举(bootstrapping)和降模(modular switching) 运算时，一般有λ ＞4N.理由如下.

由于f作为布尔函数的电路尺寸为N，且D(·，·) 的电路尺寸稍大于N′，因此f**作为布尔函数的电路尺寸稍大于N+N′.这就是说，f**是顺序做大约N+N′个布尔运算.作为f**的密文同态函数，f***应该是顺序做大约N+N′个模q运算，而且f**和f***的依次运算类型相互对应: 一个比特异或对应一个模q加法运算，一个比特与运算对应一个模q乘法运算.现在我们考虑这些模q运算所造成的全同态密文噪声尺寸的累积.设原始噪声的平均尺寸为e，考虑到全同态加密方案的安全性，一般取e为多项式大，因此设log2e ≥8 是合理的.然后设N+N′个模q运算中有大约一半是模q加法运算，另一半是模q乘法运算.模q加法会使噪声尺寸增加，但影响不大，此处忽略.模q乘积的噪声尺寸是原来噪声尺寸的乘积，因此个模q乘法得到的噪声尺寸平均大约是.而在全同态加密方案中，防止解密出错的一个前提是q ＞2·.最后我们得到

第二个观察: 当可复用garbling 方案不使用全同态加密技术中的自举和降模运算时，可复用garbling方案中的一个(属性加密，属性解密) 的计算复杂度高于一个(E(·，·)，D(·，·)) 的计算复杂度.理由如下.

注意到f***.f**中的一个布尔运算对应f***中的一个模q运算;而对于每个i1，2，···，λ，f***中的一个模q运算对应的远远不止一个布尔运算.换句话说，每个的电路尺寸都远远大于f**的电路尺寸，也就远远大于N+N′.另一方面，根据主流KP-ABE 方案的结构[13，14]，对于布尔函数中的每个布尔运算O，ABE2，i的解密算法中总有一组对应操作O′，其中O′的计算复杂度远远超过两个布尔运算的计算复杂度.我们称O′为O的拟同态运算.综上所述，一个(属性加密，属性解密) 的计算复杂度远远高于2(N+N′) 个布尔运算，而一个(E(·，·)，D(·，·)) 的计算复杂度稍高于2N′个布尔运算.

5.3 计算复杂度的比较: 不使用自举和降模运算

BHR12 方案的主要计算是大约4N个(E(·，·)，D(·，·)).可复用garbling 的主要计算是λ个(属性加密，属性解密)，全同态加密方案的(密钥生成，同态运算)，以及一个一次性garbling (仍然是一个BHR12方案).根据我们的两个观察(见5.2 小节)，可复用garbling 的计算复杂度远远高于BHR12 方案.

5.4 计算复杂度的比较: 使用自举或降模运算

综上所述，此时计算复杂度的比较非常复杂，但没有迹象显示BHR12 方案比使用自举或降模运算的可复用garbling 方案有更高的计算复杂度.