可复用Garbling 的效率分析及简化方案*

胡予濮, 刘 君, 王保仓

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

1 前言

早期的garbling 方案(我们称之为简单garbling 方案) 可以归结为两类: Bellare 等人在2012 年提出的garbling (下文简称为BHR12 garbling) 方案[9]和Ishai 等人在2000 年提出的(下文简称为IK00 garbling) 方案[10].

BHR12 garbling 方案是暴露原电路的拓扑结构, 仅仅隐藏输入值和原电路的每一步运算符号. 这一特点使得BHR12 方案非常简洁, 但同时使得BHR12 方案不可复用, 即对于同一个原电路C和多个不同的输入值x, 其计算需要多个不同的{x,C}编码方式. 换句话说, 对于同一个原电路C和多个不同的输入值x, 如果使用相同的编码方式, 就会逐渐暴露原电路的各步运算符号, 乃至暴露原电路.

IK00 garbling 方案是使用一种分支程序, 增加输出维数, 降低每个输出分量函数的次数. 每个输出分量函数仅为输入值和随机值的3 次函数; 当随机值被确定后, 每个输出分量函数仅为输入值的1 次函数.IK00 方案的尺寸庞大, 远远大于原电路的尺寸, 而且不能保证IK00 方案的尺寸是多项式尺寸. IK00 方案不仅隐藏输入值和原电路的每一步运算符号, 也似乎隐藏了原电路的拓扑结构, 因此IK00 方案具有升级为obfuscation 的趋势, 但这种隐藏难以分析.

后期的garbling 方案(我们称之为复杂garbling 方案) 集中在可复用的garbling, 使用全同态加密、密钥全同态加密、属性加密、函数加密等技术, 将不可复用的garbling 方案改造成可复用的garbling 方案[5,6]. 其中, Goldwasser 等人在2013 年构造了第一个可复用garbling (下文简称为GKP+13 可复用garbling) 方案[5].

本文论述经典GKP+13 可复用garbling 方案的效率和简化方案, 具体如下.

· 本文指出, GKP+13 可复用garbling 方案不但尺寸庞大, 而且其内部结构含有一个一次性的(即不可复用的)garbling. 换句话说, GKP+13 可复用garbling 方案实际上是不可复用的.

· 本文给出一种简化方案, 将底层的全同态加密部件从变动密钥简化为固定密钥, 其安全性没有任何损失. 简化方案消减了方案的尺寸, 虽然简化方案实际上仍然是不可复用的garbling 方案.

本文内容编排如下. 第2节是预备知识, 回顾布尔电路的一般表达式, 以及早期的BHR12 garbling 方案和IK00 garbling 方案. 第3节给出GKP+13 可复用garbling 方案. 第4节给出我们的分析和简化方案.

2 预备知识

2.1 布尔电路的一般表达式

多项式时间可计算的布尔函数一般并不适合用代数正规型来表示, 因为项的个数很可能是指数多个.最合理的表达式是按照运算顺序来表示每一步的{两个输入比特, 运算符号, 一个输出比特}. 设运算符号集为{+,×}, 其中‘‘+” 为异或, ‘‘×” 为乘积. 则n维布尔函数C(x) 的一般表达式如下.

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

· 对于i=n+ 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. 其中xN=C(x).

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

2.2 BHR12 garbling 方案[9]

Alice 取两个公开的概率分布X0和X1, 这两个概率分布能够完全区分. Alice 取一个公开的对称加密算法E(·,·), 其中的两个位置依次为明文位置和密钥位置. 对于每个i= 1,2,··· ,N-1, Alice 随机选取一个j ∈{0,1}, 然后定义Xi,0=Xj,Xi,1=X1-j. Alice 定义XN,0=X0,XN,1=X1.

2.3 IK00 garbling 方案[10] 的第一步: 分支程序

设n维布尔函数C(x) 的一般表达式为{(x1,x2,··· ,xn),xn+1;(xi,a(i),b(i),Oi),i=n+ 2,n+3,··· ,N}. 以下Alice 逐步定义对应xi的有向图, 记作G(i).

对于i ∈{1,2,··· ,n+1}, 每个G(i) 只有两个顶点, 分别称为起点和终点; 从起点到终点的有向边赋值为xi.

对于i ∈{n+2,n+3,··· ,N}, 设{G(1),G(2),··· ,G(i-1)}已经定义完毕, 在以下两种情形下分别定义G(i).

· 情形一: 如果Oi=+, 定义G(i) 为G(a(i)) 和G(b(i)) 的并联, 即G(a(i)) 与G(b(i)) 的起点合并为G(i) 的起点,G(a(i)) 与G(b(i)) 的终点合并为G(i) 的终点. 这里需要做一个合并操作, 如果某个顶点到另一个顶点的有向边有多个, 则合并为一个有向边, 其赋值为原来多个有向边的赋值之和, 即赋值之异或.

· 情形二: 如果Oi=×, 定义G(i) 为G(a(i)) 和G(b(i)) 的串联, 即G(a(i)) 的起点就是G(i) 的起点,G(a(i)) 的终点与G(b(i)) 的起点合并为一个顶点,G(b(i)) 的终点就是G(i) 的终点.

容易看出每个G(i) 都是单起点、单终点的有向无环图, 任意两个顶点之间至多有一个有向边, 任意一个有向边的赋值都是自变量x的一次函数. 设|G(i)| 代表有向图G(i) 的规模, 即顶点个数, 则有:

可见有向图G(i) 的规模呈爆炸式增长. 特别地, 当N是多项式大时,|G(N)| 未必仍然是多项式大.

2.4 IK00 garbling 方案[10] 的第二步: 随机多项式组成的矩阵

设|G(N)|=T,T多项式大. Alice 顺序做以下三步操作.

(1) 将G(N) 的T个顶点按照任何一种偏序排列, 取这样的T×T矩阵M0, 其(i,i) 元素为常数1,而当i/=j时, (i,j) 元素为有向图G(N) 的(i,j) 边赋值. 于是M0是一个主对角线为常数1 的上三角矩阵.

(2) 取矩阵M1为M0去掉第一列和最后一行的(T-1)×(T-1) 矩阵. 于是M1的行列式恰好等于C(x).

(3) 取矩阵L和R为两个行列式均为1 的(T-1)×(T-1) 随机矩阵, 记M=LM1R. 于是M的行列式恰好等于C(x). 我们称M为C(x) 的garbled 电路.

对于一组输入值x1,x2,··· ,xn, Alice 将对应的M发送给Bob. Bob 即使不知道C(x) 的拓扑结构,他仍然能够计算M的行列式.

3 GKP+13 可复用garbling 方案[5]

本节回顾GKP+13 可复用garbling 方案, 我们将分为高层结构、中层结构、底层结构来叙述该方案.不失一般性, 总设Alice 为混淆者, Bob 为计算者.

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

GKP+13 可复用garbling 方案的设计思路是, 如果对任一个多项式时间可计算的布尔函数都存在函数加密方案, 则对任一个多项式时间可计算的布尔电路都存在可复用的garbled 电路. 请注意这里并不需要某个函数类的函数加密方案, 只需要单个函数的函数加密方案(single key functional encryption).Alice 使用这个函数加密方案. Alice 还使用一个对称加密算法E(·,·), 其中的两个位置依次为明文位置和密钥位置;E(·,·) 对应的解密算法为D(·,·), 其中的两个位置依次为密文位置和密钥位置; 设解密密钥与加密密钥相同. 对于布尔电路C(x), Alice 顺序做以下四步操作.

(1) 计算C*=E(C,k0), 即将电路C的所有信息表示成一个比特串, 用对称密钥k0对其加密.

(2) 取f(x,k) = (D(C*,k))(x), 即f(x,k) 为如下电路: 先计算D(C*,k) 的值, 再以此值作为电路作用于输入值x, 得到电路输出值. 容易看出, 当k=k0时f(x,k0) =C(x); 当k为其他值时f(x,k) 与C(x) 相互独立. 设x为n维布尔向量,k为l维布尔向量, 于是(x,k) 为n+l维布尔向量.

(3) 生成一个函数加密方案, 以及方案关于此f的对应解密密钥K0. 即, 将密文用K0解密, 则得到

f(明文).

(4) 记C=(C*,K0), 将此C作为原电路C的可复用garbled 电路, 发送给Bob.

对于一个输入值x, Alice 调用函数加密方案的加密算法, 对(x,k0) 加密, 然后把密文发送给Bob.Bob 用f的对应解密密钥K0, 将密文解密为f(x,k0)=C(x).

3.2 中层结构: 函数加密= 属性加密+ 全同态加密+ 不可复用的garbling

多项式时间可计算函数的函数加密方案是否存在? 这个问题一直都是挑战. 庆幸的是, 多项式时间可计算函数的属性加密方案是现成的. 于是GKP+13 方案的设计者们自行设计了一个函数加密方案, 其结构是属性加密+ 全同态加密+ 不可复用的garbling. 需要说明的是, 此处使用的属性加密方案并非原始的属性加密, 而是属性加密2. 具体来说, 属性加密2 的解密者并不是只有当手中的函数值为1 时才能正确解密, 而是: 当手中的函数值为1 时能解密一半明文; 当手中的函数值为0 时能解密另一半明文. 不难想象, 将原始的属性加密扩展为 属性加密2 是容易的.

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

(1) 构造一个可以加密单比特明文的全同态加密方案. 其中的(全同态加密密钥, 对应的解密密钥) 作为可变参数.

(2) 取f为3.1 节中的n+l维布尔函数. 对于n+l个单比特明文, 构造它们的f函数关于n+l个全同态密文的对应同态函数f*. 请注意f*是n+l个全同态密文和全同态加密密钥的函数, 因此当(全同态加密密钥, 对应的解密密钥) 还没确定时,f*的形式已经确定了.

(3) 将f*表示为分量布尔函数的形式:f*= (f*1,f*2,··· ,f*λ), 其中每个f*i都是全同态密文和全同态加密密钥的布尔函数,λ为分量布尔函数的个数.

(4) 构造λ个 属性加密2 方案, 分别记为ABE2,1, ABE2,2,···, ABE2,λ. 其中每个方案的(属性加密密钥, 对应的解密密钥) 作为固定参数.

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

(6) 将{(f*i,ki),i= 1,2,··· ,λ}发送给Bob. 换句话说,{(f*i,ki),i= 1,2,··· ,λ}就是3.1 节中的函数加密密钥K0.

在函数加密的加密阶段, Alice 顺序做以下六步操作.

(1) 对于函数加密的明文x= (x1,x2,··· ,xn), 调用3.1 节中的对称加密密钥k0= (k0,1,k0,2,···,k0,l), 得到全同态加密的n+l个单比特明文.

(2) 临时选取全同态加密方案的(全同态加密密钥, 对应的解密密钥), 对上述n+l个单比特明文分别进行全同态加密, 得到n+l个全同态密文ψ1,ψ2,··· ,ψn+l. 记ψ=(ψ1,ψ2,··· ,ψn+l), 作为所有属性加密密文后附的标签.

(3) 计算f*(ψ,全同态加密密钥)=(f*1(ψ,全同态加密密钥),f*2(ψ,全同态加密密钥),··· ,f*λ(ψ,全同态加密密钥)), 并将其记为ψ*= (ψ*1,ψ*2,··· ,ψ*λ). 值得注意的是, 用全同态的解密密钥和解密电路就可以把ψ*解密为f(x,k0)=C(x). 但是, 全同态的解密密钥和解密电路是需要隐藏的.

我们对以上的函数加密方案做如下注解: 该方案也可以单独提炼出来, 作为独立的函数加密方案使用.此时, 密钥生成可以交给系统来做, 加密者Alice 可以不知道解密者Bob 的解密密钥K0, 但必须知道并私藏对称密钥k0和全同态解密密钥.

3.3 底层结构: 不可复用的garbling=BHR12 garbling 方案

显然, 3.2 节中所用的不可复用garbling 方案是BHR12 garbling 方案而非IK00 garbling 方案. 因此我们必须给出以下四个注解.

4 方案分析和简化方案

4.1 GKP+13 方案的效率

我们对GKP+13 可复用garbling 方案的评价是: 庞大的尺寸、一般的功能、概念上的可复用garbling、实际结构中的不可复用garbling, 原因如下.

经过我们的分析, GKP+13 可复用garbling 方案的构造过程如下. 首先, 由随机编码和对称加密算法构造出不可复用的garbling; 其次, 由一般属性加密构造 属性加密2; 再次, 由 属性加密2 和全同态加密以及不可复用的garbling 构造单函数的函数加密; 最后, 由单函数的函数加密和对称加密算法构造出可复用的garbling.

如此庞大的尺寸, 仅仅实现了可复用的garbling. 我们知道可复用的garbling 并不是密码高级功能,因为它始终需要Alice 向Bob 隐藏一部分, 泄露另一部分, 而不是Bob 自主操作, 因而其功能级别远低于多线性映射和obfuscation.

不仅如此, 每次调用GKP+13 可复用garbling 方案, 都需要调用另一个新鲜电路的不可复用garbling. 因此, GKP+13 garbling 方案是概念上的可复用garbling, 实际结构中的不可复用garbling.

4.2 GKP+13 方案的安全性漏洞和安全性冗余

4.3 GKP+13 方案的简化方案

根据4.2 节的分析, 我们的简化方案是把全同态密钥的生成从函数加密的加密阶段提前到函数加密的密钥生成阶段. 于是在函数加密的加密阶段, 无需临时生成全同态密钥, 而全同态解密密钥的保密性由不可复用garbling 的随机编码来实现, 容易看出安全性没有任何损失. 具体方案如下.

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

(1) 构造一个可以加密单比特明文的全同态加密方案, 并生成(全同态加密密钥, 对应的解密密钥) 作为固定参数.

5 结论

本文深入探索了GKP+13 可复用garbling 方案的构造过程和安全性, 指出该方案本质上是不可复用的, 并提出一种简化方案以降低原方案的尺寸. 未来我们将研究其它garbling 方案的可复用性, 特别地,我们将证明IK00 garbling 方案也不可复用.