多属性环境下基于容错学习的全同态加密方案
2018-07-25白平,张薇
白 平,张 薇
(1.武警工程大学密码工程学院,西安710086; 2.武警工程大学信息安全保密重点实验室,西安710086)(*通信作者电子邮箱bp15771937011@163.com)
0 引言
近年来,随着云计算技术[1]快速发展,大量用户将个人隐私数据存放或运行在外部云服务器上,然而,用户在获得便利的同时,数据共享、隐私保护等相关一系列问题逐渐凸显出来。至今为止,在实际应用中这些问题依然没有找到一种高效且实用的解决办法,有关云计算安全问题依然是密码学界的研究热点。为了能很好地解决上述问题,在密码学领域中“全同态加密”技术应运而生。2009年,Gentry[2]提出基于理想格(Ideal Lattice)上的最短向量问题(Shortest Vector Problem,SVP),构造出了第一代能够真正实现全同态加密的体制。此后,对于全同态密码的研究便成为了密码学界一个新的研究热点[3-6]。
2011 年,Brakerski等[7]提出基于容错学习(Learning With Errors,LWE)困难问题的全同态加密体制,基于LWE问题的公钥加密体制继承了格上密码体制的优势,且具有简单的计算形式。2013年,Gentry等[8]提出了一种全新的层次型全同态加密方案(GSW13方案),这个方案优点在于摆脱了Gentry框架而完全基于LWE问题,去除了运算密钥,利用“近似特征向量”的技术实现矩阵同态加法和矩阵同态乘法的特性,从而实现了层次型全同态。属性加密最初由Sahai等[9]在2005年提出,是一种具有良好访问控制特性的加密方式,具有如下3个优良的性质:1)加密者只需知道明文对应的属性即可加密,无需了解明文消息的具体内容,从而在一定程度上保护了用户隐私;2)只有正确掌握属性信息的用户才能够解密,从而保证数据的安全性;3)基于属性加密(Attribute Based Encryption,ABE)机制支持基于属性的灵活访问控制策略,可以实现属性的与、或、非和门限操作。在属性加密系统中,密文不需要以传统的公钥密码体制加密给一个特定用户,而是用户的私钥和密文与一个属性集或属性上的策略相关联,当且仅当用户的私钥和密文相匹配时,用户才能够解密得到正确的明文。
本文针对 Gentry、Sahai和 Waters[8]描述的 GSW13 编译器只能够在单属性环境下工作的不足,通过借鉴“模糊系统”技术实现了多属性环境下的全同态加密。实现多属性加密主要有以下两层意义:1)对于单个用户来说,属性个数的增加能够很好地增强用户外包数据的访问控制权限,从而减少用户外包数据泄露的概率。2)对于多个用户来说,能够在保证各自用户数据不泄露的情况下,实现在不同的属性加密情况下,多个用户可以共享彼此外包数据,从而实现了数据的最大利用率。此外,构造的方案可以实现如下功能:可以将满足一定属性要求的ABE方案转换成多属性环境下的全同态加密方案,进一步提高了用户外包数据的安全性和实用性,提升了全同态加密在云计算外包过程中的运用。
1 预备知识
1.1 容错学习问题[10]
在正式定义LWE之前,首先介绍几个相关的概率分布:
1)将整数域Zq上以0为中心为标准差的离散正态分布称为“误差分布”,记为χ。
定义1 设定模数q=q(χ),存在矩阵A和向量v,使得v=As+e,其中A∈Znq,s∈Zq分别在Znq和Zq中依均匀分布随机选择,小变量 e在Znq上服从误差分布 χ。LWEn,m,q,χ问题可描述为:给出m个As,χ分布上相互独立的变量,求其对应的向量 s。
1.2 基于属性的同态加密方案体制模型
一个基于属性的同态加密体制为 ABHE=(Setup,KeyGen,Enc,Dec,Eval),主要由以下5个具体算法构成:
初始化算法Setup(1λ)。输入安全参数λ,输出公开参数params和用户主私钥MSK。定义一个环R、函数集F和计算关系式:R(x,y),x ∈ {0,1}k,y∈ {0,1}l,其中 k,l为任意参数。设定运算电路为 Ω:{0,1}t→ {0,1},电路深度为 L。
私钥生成算法KeyGen(MSK,y)。由主私钥MSK和参数y生成用户私钥sky,其中y∈{0,1}l。随后对属性x进行哈希运算得到用户公钥pkx,x∈{0,1}k,将用户私钥sky返回给拥有属性x的用户。
加密算法 Enc(params,pkx,μ)。输入公开参数params、用户公钥pkx和明文消息μ,输出密文c。
解密算法 Dec(sky,c')。若满足式 R(x,y)=1,则可根据用户私钥sky和密文c',解密得到明文μ';若R(x,y)≠1,则解密中止,输出无效符号⊥。
密文运算算法 Eval(params,Ω,c1,c2,…,ct)。由公开参数params、事先设定的运算电路Ω以及用相同属性值x加密的一组密文{c1,c2,…,ct},输出一个新密文 c',即 Ω(c1,c2,…,ct) → c'。
定义2 假设ξ表示一个满足以下3个属性的ABE方案:
1)属性x对应的解密密钥sky和密文c都是Zm'q上的向量,并且sky的第一个元素系数是1。
2)如果c是明文0对应的密文,则〈cx,sky〉是比较小的。
3)对明文0的加密结果与Zq上的一般向量不可区分。
则ξ的模糊系统 OSξ可表示为 OSξ=(GenUnivObs,DeriveObs),其中两个概率多项式时间算法满足如下定义:
1)GenUnivObs(params,id,μ)。输入方案 ξ的公共参数params、属性信息x和明文μ∈{0,1},输出泛模糊信息U∈{0,1}*。
2)DeriveObs(params,U,x')。输入方案 ξ的公共参数params,泛模糊信息U∈{0,1}*和一个属性信息x',输出一对矩阵
上述定义的模糊系统OSξ满足以下属性:
正确性 对于任意(params,MSK)← ξ.Setup(1λ),任意属性信息x,x',私钥vx=Powerof2(x.KeyGen(MSK,x)) ∈和 vx'=Powerof2(ξ.KeyGen(msk,x')) ∈ ZNq,明文 μ ∈ {0,1}以及所有的 U ← GenUnivObs(params,x,μ)和(X,Y)←DeriveObs(params,U,x'),均满足如下的关系式:其中e为允许范围内极小误差值。
安全性 在改进过的方案ξ的基于X不可区分的选择明文攻击(INDistinguishability-X-Chosen Plain Attack,IND-XCPA)游戏中,所有的概率多项式时间攻击者以可忽略的优势取胜,则称模糊系统是安全的。改进的IND-X-CPA游戏所做的唯一改变是将原来游戏中的挑战密文更换为U*←GenUnivObs(params,x*,μb),其中是挑战者所选的随机比特位,x*是攻击者所选的攻击属性,μ0,μ1是由攻击者所选择的挑战明文。
1.3 GSW13方案构造过程
2013年,Gentry等[8]提出了一个新的基于LWE困难假设的全同态加密体制(简称GSW13方案),这个方案的优点在于只需要一些系统基本参数就能够实现方案的同态运算操作,消除了以往方案中对解密密钥的依赖。这一技术的突破使得构造全同态加密体制迈进了一大步,使得在真正意义上实现全同态加密成为了可能。具体的算法过程如下:
密钥生成算法KeyGen(params,λ,L)主要分为如下3个算法。
1)参数生成算法Setup(1λ,1L)。选择一个模数q,并且模数q位数大小为κ=κ(λ,L)比特,格的大小n由函数n=n(λ,L)生成,容错学习(LWE)问题中的误差分布记为:χ=χ(λ,L)。选取参数 m=m(λ,L)=O(n lb q),则令 params=(n,q,χ,m),l=?lb q」+1,N=(n+1)·l。
2)私钥生成算法SecretKeyGen(params)。从Znq中选取一个参数作为样本,记为t,输出私钥sk=s←(1,-t1,…,-tn)∈Zn+1q。同时,令v=Powerof2(s)。
3)公钥生成算法 PublicKeyGen(params,sk)。产生矩阵B ←Zm×nq和向量e←χm。令b=B·t+e,e表示一个误差向量,A可表示为由矩阵B和矩阵b的第n+1列所组成的矩阵,即Am×(n+1)=(B,b)。公钥 pk=A。
加密算法 Encrypt(params,pk,μ)。
选择明文消息μ∈Zq和由数字0和1两种元素组成的矩阵Q,输出密文矩阵:
C=Flatten(μ·IN+BitDecomp(Q·A)) ∈ ZN×Nq其中IN为N维单位矩阵。
解密算法 Decrypt(params,sk,C)。
记私钥生成算法SecretKeyGen(params)中得到的向量v的前 l个元素系数为 1,2,…,2l-1,从中选取满足 vl=2l∈(q/4,q/2]的系数并标记为 i,计算 xi←〈Ci,v〉= μ·vi+e,其中Ci代表密文C的第i行。由于e表示一个小误差向量,vi则表示一个拥有大系数的N维向量,故可以通过μ'=?xi/vi」来解密求得明文μ'。
下面简要介绍一下GSW13方案同态操作。
GSW13方案的同态性质主要分为以下4个部分:乘以常量的同态操作MultConst、加法同态操作Add、乘法同态操作Mult和与非门运算时同态操作NAND。
1)MultConst:
用已知常量α∈Zq同密文矩阵C∈ZN×Nq进行相乘运算,定义 Mα←Flatten(α·IN),输出 Flatten(Mα·C)。
由于e是一个可忽略不计的小误差向量,所以对于密文矩阵C的常量乘等于明文的常量乘,能够满足正确解密的条件。
2)Add(C1,C2):
对于密文 C1,C2∈ ZN×Nq
可以看出误差的增长主要来源来误差向量e1+e2增长,这不会影响解密操作。
3)Mult(C1,C2):
对于密文 C1,C2∈ ZN×Nq,有:
在乘法同态的运算中可以看出,新的误差增长主要来源于密文矩阵C1和明文消息μ2。由于矩阵C1已经在加密过程中被限制C1∈{0,1}中,主要的目标是要限制明文消息μ2的增长。为此,可以引入布尔电路,通过与非门将其限制在{0,1}中,从而保证乘法同态运算的正确性。
4)NAND(C1,C2):
对于密文 C1,C2∈ ZN×Nq,则
对于与非操作,同态操作的正确性取决于μ2·e1-C1·e2的大小,只要保持明文μ2在{0,1}范围内,则可保证操作运算的正确性。
1.4 扁平技术
如果C1和C2分别是明文消息 μ1∈{0,1}和μ2∈{0,1} 对应的密文矩阵,即 Cj·v= μj·v+ej(其中 j∈ {0,1},ej表示极小误差向量),两个密文矩阵的上界为B。则加法同态C+=C1+C2以2B为界限,乘法同态C×=C1·C2以(N+1)B2为界限。为了确保运算操作过程中的正确性,使得解密结果保持在{0,1}范围内。因此需要运算其他技术手段来保持密文矩阵的每一项都足够小,本文借鉴文献[11]提出的一种被称为“扁平技术”的Flatten操作。
定义a和b是维度大小为k的向量,设定l=?lb q」+1、N= k · l 和 BitDecomp(a) =(a1,0,…,a1,l-1,…,ak,0,…,ak,l-1),其中 ai,j是指 ai二进制中的第 j位。同时,令 a'=(a1,0,…,a1,l-1,…,ak,0,…,ak,l-1),则 BitDecomp 的逆可表示为 BitDecomp-1(a')=假如输出结果不在有效的解密范围{0,1}内,则令Flatten(a')=BitDecomp(BitDecomp-1(a')),其中 a'表示 N 维{0,1} 的向量。BitDecomp(A),BitDecomp-1(A) 和 Flatten(A) 对于矩阵A的操作是对A的每一行进行单独操作。令Powerof2(b)=(b1,2b1,…,2l-1b1,…,bk,2bk,…,2l-1bk),其结果是一个 N 维{0,1} 向量。
具有如下两个性质:
1) 〈BitDecomp(a),Powerof2(b)〉=〈a,b〉
2)对于任意N维向量a',有如下等式:
〈a',Powerof2(b)〉=〈BitDecomp-1(a'),b〉=
〈Flatten(a'),Powerof2(b')〉
1.5 密文扩展算法
为了能够满足GSW13方案中所要求的矩阵形式,经过不同属性值加密所得的密文矩阵需要经过必要的转换才能符合要求。定义由不同属性xi(i=1,2,…,υ)加密明文μ得到的密文矩阵为 Ci(i=1,2,…,υ),用 C^ ∈ ZυN×υNq表示相对应的“扩展矩阵”,同时要求这个扩展矩阵必须满足如下形式:
对于:
1)计算 (Xi+Yj) ← OSξ.DeriveObs(params,U,xi);
2)设置 C^i,j← Yi;
3)设置 C^i,j← Flatten(C^i,j+Xi)。
2 应用场景分析和系统模型构建
2.1 多属性环境下全同态加密方案应用场景
考虑这样一个具体的应用场景:设想A和B均是某公司的员工,但是A和B不在同一个地方工作。假如现在公司要求A和B共同来完成一个项目,A和B为了更加便利地分享彼此的信息,通常会将各自的数据资料加密后存储在不完全可信的第三方云服务器E上,其中A和B的数据资料是分别使用各自的属性信息生成的私钥skxA和skxB进行加密的。本文想要实现这样一个目的:允许A和B对彼此的加密的密文进行某些运算操作,用C表示运算后的密文。根据以上的描述可知所得的密文C是使用了A和B各自的属性信息密钥共同加密的,所以计算结果只能由A和B共同解密。具体如图1所示。
针对Gentry,Sahai和Waters提出的基于LWE全同态加密方案中只能在单属性环境下工作的局限性的问题,本文主要想解决的问题是突破方案中单个属性的限制,构造一个在多属性环境下的全同态方案。设想这样一个实际的环境:用户A使用属性x1对明文消息μ1∈{0,1}进行加密得到密文矩阵CT1,用户B使用属性x2对明文消息μ2∈{0,1}进行加密得到密文矩阵CT2。假如想要实现2.1节中所提的目的,那么具体操作步骤如下:第一步是将得到的两个密文矩阵CT1和CT2运用某种方法进行转换;第二步是将转换得到的结果输入到运算电路Ω中。显然,可以得到一个新的密文矩阵C^',其对应的新明文为 μ'= Ω(μ1,μ2),根据GSW13方案的构造框架,可以表示为:
其中small表示可忽略的一个参数。
在上述具体操作过程中,可以发现存在的主要问题在于第一步中如何对不同的密文矩阵进行变换?由于加密的属性信息x1≠x2的原因,产生的密文矩阵Ci(i=1,2)也是不同,故不能直接进行加乘运算。需要借助其他有效方法进行转换,以期满足同态的紧凑性条件。本方案的主要思想是通过借助“模糊系统”技术将不同的密文矩阵转换成相应的“扩展矩阵”以满足GSW13构造框架中C^'。
图1 加密方案应用场景Fig.1 Application scene of encryption scheme
2.2 多属性环境下基于LWE全同态加密方案的系统模型
本方案主要是在属性加密方案(ABE)基础上进行扩展延伸的,普通的ABE方案通过GSW13编译器可以转换为单个属性环境下不完全的全同态加密方案,更进一步如果符合定义2所描述的3个属性,则可进一步转换成单个属性环境下可自举不完全的全同态加密方案,本方案的改进地方是在可自举的方案的基础上继续借鉴一种称为“模糊系统”的技术,将方案转换为可以在多个属性环境下的不完全的全同态加密方案。为了直观了解本方案的构造过程,下面用图2进行说明。
图2 系统模型示意图Fig.2 Schematic diagram of system model
3 基于LWE的全同态加密方案
3.1 方案构造
基于2.2节中所提出的系统模型,下面将构造一个方案,目标是将属性符合定义2中要求的ABE方案能够转化成支持多属性环境下的全同态加密方案。方案ξMAS主要包括以下5个算法,分别描述如下:
初始化算法 ξMAS.Setup(1λ)。输入安全参数 λ,输出公开参数params和系统主私钥MSK。选取f∈F,定义用户属性集合为 I={x1,x2,…,xυ},随机选取参数 y,要求满足等式R(xi∈I,y)=1。
私钥生成算法 ξMAS.KeyGen(MSK,y)。由系统主私钥MSK和参数y∈{0,1}*,生成得到用户的一个私钥sky,将此私钥返回给拥有属性xi,i∈{1,2,…,υ}并且满足条件等式R(xi,y)=1 的用户。
加密算法 ξMAS.Enc(params,xi,μ)。输入明文 μ 和属性信息 xi, 运 行 加 密 机 得 到 泛 模 糊 信 息:U ←OSξ.GenUnivObs(params,xi,μ),输出密文 CT=(xi,type=0,enc=U)。其中type=0表示“刷新过的”密文。
密文运算算法 ξMAS.Eval(Ω,CT1,CT2,…,CTυ)。输入CTj=(xi,type=0,enc=Uj),i=1,2,…,υ,不同属性的集合为 I=(x1,x2,…,xυ),用=υ表示属性集合中属性的数
解密算法 ξMAS·Dec(vx1,vx2,…,vxk,CT=(x1,x2,…,xυ,type,enc))。输入密文 CT=(x1,x2,…,xυ,type,enc) 和私钥序列vx1,vx2,…,vxυ(其中vxi是指属性xi对应的向量私钥,其中i∈解密机通过执行以下步骤可以得到泛模糊信息。垂直连接排列列向量vx1,vx2,…,vxυ组成向量v。
1)若type=0,则enc表示泛模糊信息U,计算(X,Y)←OSξ.DeriveObs(params,xi,U),并且设置 C ← X+Y;
2)若type=1,则enc表示C^并且设置C←C^;
选择满足 vi=2i∈ (q/4,q/2]的 i,计算 di←〈ci,v〉=μ·vi+e,其中 ci是指矩阵 C 的第 i行,输出 μ'←?di/vi」∈{0,1},其中μ'表示解密恢复的明文消息。
3.2 方案正确性分析
为了更好地说明方案的正确性,可以通过实例进行说明:令υ=2,j=1。将两个不同的属性值输入同一种加密机(加密机没有硬性规定,只要是同一种即可)中得到密文矩阵分别满足 CT1·vx1= μ1·vx1+e1和 CT2·vx2= μ2·vx2+e2,其中 vx1=Powerof2(x1),vx2=Powerof2(x2)。运用1.5 节中的密文扩展算法将这两个密文矩阵CTi都转换成如下形式:量。在运算执行之前,必须对每个密文矩阵CTi运行密文扩展算法将其转换成符合要求相对应的υN×υN扩展矩阵C^,而后使用运算电路Ω对扩展矩阵C^进行与非门操作运算,产生符合GSW13构造框架中所要求的矩阵C^'。假设每个 C^对应的明文消息是μi∈{0,1},则 C^'对应的明文消息是C(μ1,μ2,…,μυ)。最后,密文运算算法输出的密文形式为CT'=(x1,x2,…,xυ,type=1,enc=C^'),其中 type=1 表示是一个运算密文。
经过转换后的密文形式具有相同的形式,故可以进行同态的加乘运算,最后将C^输入到预先设定的运算电路中即可。同样在解密过程中,可以用和加密机相对应的解密机进行解密,解密机通过判断密文中type的值,从而确定所求密文矩阵,最后计算 di←〈ci,v〉= μ·vi+e和μ'←?di/vi」∈{0,1},则可以得到明文消息μ'。
4 方案的分析
4.1 安全性分析
该方案构造的多属性环境下的全同态加密方案与普通的基于属性的加密方案相比除了在属性的数量上有所增加外,主要区别是增加了一个密文运算算法 ξMAS.Eval(Ω,CT1,CT2,…,CTυ)。然而,此算法的增加并不会影响基于属性加密方案的安全性[12],故该方案的安全性证明类似于属性加密方案的安全性证明。在确保方案安全性的基础上,本文还要在同态运算为与非操作的可行性进行证明。
定义3 多项式函数μ(x):Ν→R,如果对于任何一个正多项式poly(n),有一个自然数 c,使得对于所有 x>c,有μ(x) <[1/poly(x)],则称函数μ是可忽略的,记为negl(x)。
初始化 挑战者B执行初始化算法Setup(1λ),生成公开参数params,系统主私钥MSK,将params发送给敌手A。
阶段1 敌手A随意选择两个长度相等的明文(μ1,μ2)和一个挑战属性信息x*发送给挑战者B,而后敌手A对不同的属性信息xi所对应的私钥进行询问。挑战者B通过调用私钥生成算法KeyGen(MSK,y)得到相应的sky,随后发送给敌手A。
挑战过程 敌手A随意选择两个长度相等的明文(μ1,μ2)和一个挑战属性信息x*发送给挑战者B,其中x*xi,即属性信息x*不存在于属性集合I={x1,x2,…,xυ}中。挑战者B随机选取明文下角标b∈{0,1},用属性信息x*对μi进行加密,得到目标密文Enc(params,pkx,μ)→c,并将其发送给敌手A。
阶段2 挑战者B继续给敌手A发送属性信息xi的私钥sky,敌手A适应性地选择挑战者B的输入。要求x*I={x1,x2,…,xυ}。
猜测过程 敌手A猜测目标密文c所对应的明文,输出相应的b'作为敌手A的猜测结果。
定义4 B界分布。令B<q代表一个整数,对于C·v=μ·v+e,如果μ的量级不大于B,则称密文C对于v是B为界的,C的每一项的量级不大于B,并且‖e‖∞≤B。
定理1 设L和D均为正整数,w为误差因子,如果q>8w·B(DN+1)L,则方案ξMAS是正确的,并且对任意υ≤D个不同的属性,都可以进行深度为L的与非正确运算。
证明 设υ≤D个不同的属性x1,x2,…,xυ参与运算,与属性xi,i∈υ相关的“刷新过的”新密文为CT=(xi,type=0,enc=U),由这些新密文转换得到扩展矩阵,将v1,v2,…,vυ按照列的形式串联组成向量^v,C^表示CT对应的扩展矩阵,用对 应 的 属 性 信 息 x1,x2,…,xυ计 算 (Xj,Yj) ← OSξ.DeriveObs(params,U,xj),根据构造过程,C^包含υ × υ个ZN×Nq上子矩阵,其中N-1行都包含两个非零子矩阵,只有第i行包含一个非零子矩阵。则可得到如下等式:
由于每个子矩阵都满足定义4中的B界分布,因此C^·^v=μ·^v+^e的误差向量^e的系数是以w·B为界的。在与非运算中乘以 υN×υN个扩展矩阵的操作会产生一个以B(υN+1)为强界的矩阵。连续进行L次同态运算后,误差的界限变成w·B(υN+1)L。为了正确解密需要满足条件w·B(υN+1)L< q/8,由 υ≤D。故可知:
w·B(υN+1)L≤ w·B(DN+1)L≤
[8·w·B(DN+1)L]/8≤ q/8
4.2 性能分析
Gentry等[8]提出了基于LWE的全同态加密方案,本方案是在GSW13方案的基础上进行了改进,实现在多属性环境下的全同态加密。本方案与GSW13方案有相同点和不同点。与GSW13相比,两个方案的相同点是方案都是基于LWE困难性假设进行讨论的。另外,与GSW13方案相比,主要有以下几点不同地方:1)本方案在工作环境方面较GSW13有一定的提高,可以支持在多属性环境下的全同态加密方案,克服了GSW13方案中单个属性的局限性。2)在安全性方面,本文除了对安全性进行了必要的证明,同时对方案的正确性和进行与非门操作时的可行性进行了说明。3)在效率方面,由于将单个属性扩展到多个属性的缘故,整个方案中增加了一些参数:如运算电路可支持的最大属性值模糊系统中的参数、矩阵等,导致了效率较GSW13有所下降。由于全同态加密方案普遍效率比较低,距离真正实际应用还有一定距离,本文在性能分析描述中对效率没有作具体的量化,其中效率的高低只是3个方案的相对比较。具体对比如表1。
表1 几种加密方案性能对比分析Tab.1 Performance comparison analysis of several encryption schemes
通过表1可以得出,本方案与文献[8]中Gentry的方案相比,优点是能够支持在多个属性环境下的全同态加密操作,实现在保证不同用户数据不被泄露的情况下,使得拥有不同属性值的多个用户共享彼此的隐私信息,实现了用户数据的最大利用率,从而在一定程度上增强了外包用户数据的可操作性,扩展了全同态加密在云环境领域中的应用范围。
5 结语
本文通过将模糊系统技术引入到GSW13方案中,构造了一个适用于云环境的多属性环境下基于LWE的全同态加密方案,通过利用模糊系统的特性,主要解决了不同用户的外包数据的共享性问题,提高了用户外包数据的实用价值。下一步的工作是探索能够适用于本方案的具体实例环境,构造出真正意义能够实际应用的全同态加密方案。