云计算是当前非常流行的新型IT技术,代表着IT领域迅速向集约化、专业化发展的趋势.由于云计算的通用性及便利性,它得到大力推动和发展.但隐私保护问题与便利性的冲突已经成为制约云计算发展的重要因素,即:用户希望在享受云服务器便利性的同时,也可以保护自己的隐私不外泄.全同态加密体制允许服务器在不解密的条件下对数据进行有效运算,因此它成为解决上述冲突的一个重要方案.

但已有的全同态加密体制普遍存在密文运算效率低、公钥尺寸过大的问题,如何有效管理密钥,一直是体制应用面临的难题之一.基于身份加密利用用户的唯一身份标识(如电子邮箱地址等)作为公钥,用户私钥的生成由可信第三方来完成(可信第三方由云服务器提供或用户自行选取),具备不依赖公钥证书进行密钥管理的优点,因此,人们开始思考如何将基于身份加密的思想与全同态加密技术结合起来.但是以往基于身份的全同态加密体制(以下简称IBFHE体制)都必须借助运算密钥(evaluation key),无法实现真正意义上的IBFHE体制.直到2013年,Gentry等人舍弃了运算密钥,利用特征向量方法构造了第一个真正意义上的IBFHE体制.这些体制大多以特殊分圆环作为基本代数结构,虽然特殊分圆环结构简单,使用方便,但在构造体制时,计算效率较低,无法使用SIMD等技术.因此,本文提出了任意分圆环上的陷门,借助该陷门和特征向量方法,提出了IBFHE体制.相比Gentry提出的环上IBFHE体制(以下简称GSW体制),本文的体制最多可将密文运算效率提升一倍.另外,以任意分圆环作为基本代数结构,还可应用SIMD技术,使得每个密文可对应多份明文,大大提升空间和计算效率.

本文第1节介绍目前有关全同态加密的相关工作.第2节介绍本文体制所需的基础知识.第3节首先给出构造本文体制所需要的基本公钥体制,再给出任意分圆环上特征向量体制并证明其正确性和安全性.第4节首先给出任意环上的陷门,然后构造任意分圆环上使用特征向量的基于身份加密体制,最后证明任意环上FHE体制到IBFHE体制的转换定理.第5节对以上内容作出总结.

1 相关工作

全同态加密(fully homomorphic encryption,简称FHE)由Rivest等人^[1]在1978年首次提出,若某种加密体制对各种运算都满足同态性质,意为密文进行某种运算后进行解密,得到的明文恰好是对应明文的运算结果.尽管概念简单,但全同态加密的设计实现难度很大.直到2009年,Gentry在其博士论文^[2]中基于理想格成功构造出第一个真正意义上的全同态加密体制(gentry体制),使得该领域得到突破性进展.接下来的几年里,全同态领域的研究突飞猛进,各种全同态加密体制纷纷出现.

1.1 全同态加密体制研究现状

目前的全同态加密体制根据基于的数学难题及代数结构不同,大致分为以下几类:(1) 基于理想格的全同态加密体制;(2) 整数上的全同态加密体制;(3) 基于LWE(learning with error)问题的全同态加密体制;(4) 基于RLWE(环上LWE)问题的全同态加密体制.

(1) 基于理想格的全同态加密体制

虽然首次实现了全同态加密体制,但Gentry体制的密文运算计算复杂度过高、公钥尺寸过大.为了得到性能更好的全同态加密体制,以达到高效实用的最终目的,全同态加密初期研究的大量成果可归结为Gentry体制的优化方案.针对Gentry体制公钥尺寸过大的问题,Smart等人^[3]提出优化方案,称为SV体制,SV体制公钥尺寸很小,但密钥生成算法复杂度过高.借用SV体制的思想,Gentry等人^[24]给出Gentry加密体制的另一种优化方案,称为GH体制,GH体制使用主理想格作基础,并使用SV体制中的公钥形式,但对密钥生成过程进行了简化.随后,Smart等人^[5]提出了SIMD技术:SIMD技术本质上是一种并行思想,在SV体制和GH体制的基础上,使用中国剩余定理对明文空间进行分解,使得每份密文对应多份相互独立的明文,所以,利用SIMD技术可以减小单位明文对应的密文尺寸,更高效地利用空间和计算资源.

(2) 整数上的全同态加密体制

2009年,Van Dijk等人^[4]提出一种新的全同态加密体制,该体制基于整数上近似最大公因子问题,称为DGHV体制.该体制结构简单,便于理解,但公钥尺寸极大,效率较低,无法满足实际应用的需求.到目前为止,Stehlé等人在文献^[7]中构造的体制计算复杂度约为W(l³⁵)(l为体制安全参数),该体制在此类体制中的优化已达到较好效果.此类体制沿用Gentry博士论文中设计全同态加密体制的方法(以下称Gentry方法),但基于该方法设计的体制的安全性必须依赖一个额外的假设,即,稀疏子集合假设(sparse subset sum assumption,简称SSSP),但该假设的强度缺乏严格证明.另外,Gentry方法需要大量密文同态运算,因此,使用Gentry方法设计的全同态加密体制的计算复杂度很难降低.

(3) 基于LWE问题的全同态加密体制(以下简称LWE体制)

理想格上很多困难问题的难解性并未得到证明,因此,这类体制在安全性方法上也有一定的隐患.2011年,Brakerski和Vaikuntanathan^[8]构造了基于一般格上困难问题的全同态加密体制,称为BV体制,BV体制基于LWE问题^[9].与理想格上的体制相比,BV体制使用的LWE问题难解性得到了严格证明^{[8, 10]},并且BV体制的解密运算计算复杂度低.Brakerski等人^[11]又在此基础上提出密钥转换(key switching)技术,实现对密文噪声的精确控制,使得BV体制的计算复杂度极大地降低.

(4) 基于RLWE问题的全同态加密体制(以下简称RLWE体制)

2010年,Lyubashevsky等人^[12]首先定义了RLWE问题,RLWE问题与LWE问题结构相似,因此许多优化方法可以通用于两类体制.而且,RLWE体制相对于LWE体制在很多加密应用中具有优势:首先,LWE体制在一些实际应用中效率不高(例如构造单向函数);其次,RLWE体制中的带噪声乘法可以一次直接得到$\mathbb{Z}$_q上n个伪随机结果,相当于LWE体制中的n次乘法;再次,若使用快速傅立叶变换,那么RLWE体制中乘法效率会更高;最后,使用环中理想对应的格时,可以用标准嵌入(canonical embedding)来代替系数嵌入(coefficient embedding),进一步减少密文尺寸.目前的RLWE体制根据使用的环类别不同而分为两类:

i. 第1类使用的是特殊环,其分圆多项式的次数为2的方幂.

由于其结构简单,易于理解,并且具备上面提到的所有优点,故Brakerski和Vaikuntanathan^[13]按照构造基于LWE问题体制的思路,构造基于RLWE问题的全同态加密体制.随后,Brakerski等人^[11]又将LWE问题与RLWE问题统一起来,称为GLWE问题,并借此构造了一个基于GLWE问题的全同态加密体制.

ii. 第2类使用的是任意环,即,分圆多项式的次数可以取任意值.

特殊环代数结构简单,但同时也牺牲了很多性质:首先,特殊环分布稀疏,在同样满足安全性的前提下,使用任意环的体制会比使用特殊环的体制效率高最多一倍;第二,特殊环上的体制无法实现SIMD等技术,无法进一步提高效率.但任意环上的实用算法和分析工具很少,仅有Lyubashevsky等人^[14]提出的一些算法和工具,故,虽然使用任意环效率很高,但后续的研究较少.

1.2 基于身份的全同态加密体制

1984年,Shamir^[15]首次提出了基于身份的加密(identity-based encryption,简称IBE)体制,这是一种不需要证书的公钥加密体制.每个用户都拥有唯一的公开身份信息,用户公钥由此信息生成,所以不需要认证,而用户私钥由可信第三方生成.由于无须公钥证书,所以IBE体制避免了与证书有关的计算和存储,可以更有效地管理密钥,减小密钥尺寸.但直到2001年,可应用于实际的IBE体制设计方法才由Boneh等人^[16]与Cocks等人^[17]分别提出.文献^{[16, 17]}的方法分别基于双线性映射函数构造和二次剩余假设.近年来,格上的难题也被应用于构造基于身份加密体制,2008年,Gentry等人^[18]在Regev加密体制^[9]的基础上提出了IBE体制,并证明了其CPA安全性.

因此,人们自然地想到构造基于身份的全同态加密体制,将基于身份加密体制与全同态加密体制相结合,利用基于身份加密体制的优势来进一步提高全同态加密体制的效率.在研究的初期,IBFHE体制都需要借助运算密钥来实现,并非真正意义上的基于身份加密体制,如文献^[19].2013年,Gentry等人在文献^[20]中提出了特征向量方法,成功地避免运算密钥,实现了真正意义上的IBFHE体制.另外,Gentry也简要给出了在特殊分圆环上该体制的形式.

2 预备知识

对于正整数k,定义[k]为集合{0,…,k-1};对于$\mathbb{R}$ⁿ或$\mathbb{C}$ⁿ上的向量x,定义其l₂范数为$||x|{|_2} = {\left( {\sum\nolimits_i {|{x_i}{|^2}} } \right)^{1/2}}$,l_∞范数为||x||_∞=max_i|x_i|.记$\mathbb{Z}_m^*$为比m小且与m互质的正整数集合,ϕ(⋅)为欧拉函数.

空间${\mathbb{C}^{\mathbb{Z}_m^*}}$定义为${\mathbb{C}^{\mathbb{Z}_m^*}} = \{ x = ({x_{{i_1}}},...,{x_{{i_{\varphi (m)}}}})\} $,i_j为$\mathbb{Z}_m^*$中第j个元素,j∈[1,…,ϕ(m)].空间$H \subseteq {\mathbb{C}^{\mathbb{Z}_m^*}}$定义为$H = \{ x \in {\mathbb{C}^{\mathbb{Z}_m^*}}|{x_i} = \overline {{x_{m - i}}} ,\forall i \in \mathbb{Z}_m^*\} $,在研究以分圆数域和理想格构造的加密体制时,使用该空间较为方便.

2.1 格基础

H中的格可定义为H的离散加法子群,由n个线性无关向量B={b_j}⊂H的所有整线性组合构成的集合,即$\Lambda = \Lambda (B) = \left\{ {\sum\nolimits_j {{z_j}{b_j}:{z_j} \in \mathbb{Z}} } \right\}$;两组基B,B′生成同一个格当且仅当存在一个幺模矩阵U,使得BU=B′;L(B)的行列式与基的选取无关,定义为任意一组格基矩阵的行列式(如|det(B)|);在欧式范数下,L的第1小量定义为格中最短非零向量长度:l₁(L)=min_0x∈L||x||₂.L的对偶格定义为${\Lambda ^ \vee } = \left\{ {y \in H:\forall x \in \Lambda ,\langle x,\bar y\rangle = \sum\nolimits_i {{x_i}{y_i} \in \mathbb{Z}} } \right\}$.容易看出:

${({ \wedge ^ \vee })^ \vee } = \wedge .$

对于s＞0,定义高斯函数p_s:H←(0,1]为${\rho _s}(x) = \exp ( - \pi \langle x,x\rangle /{s^2}) = \exp ( - \pi ||x||_2^2/{s^2})$.归一化该函数就可得到连续高斯分布D_s,其概率密度为s^-n⋅p_s(x).

定义1. 对于H中任一向量c,有格陪集Λ+c和实数s＞0,可定义Λ+c上的离散高斯分布为

${D_{\Lambda + c,s}}(x) = \frac{{{\rho _s}(x)}}{{{\rho _s}(\Lambda + c)}}$

2.2 分圆域(环)性质

对于正数数m,在有理数域中添加m次本原单位根ζ_m,得到的域扩张K=$\mathbb{Q}$(ζ_m)称为m次分圆数域,ζ_m的极小多项式定义为m次分圆数域:

${\phi _m}(x) = \prod\nolimits_{i \in \mathbb{Z}_m^*} {(x - \omega _m^i) \in \mathbb{Z}[x]} ,$

其中,w_m∈$\mathbb{C}$是$\mathbb{C}$中m次本原单位根(例如${\omega _m} = \exp \left( {2\pi \sqrt { - 1} /m} \right)$,故K与$\mathbb{Q}$(x)/(φ_m(x))存在一个自然同构,由ζ_m→x给出.φ_m(x)的次数为$n = |\mathbb{Z}_m^*| = \varphi (m)$,故可将K看作$\mathbb{Q}$上n维向量空间,并以${(\zeta _m^j)_{j \in [n]}} = (1,{\zeta _m},...,\zeta _m^{n - 1}) \in {K^{[n]}}$作为一组基,这组基称为幂基(power basis).所谓特殊分圆环,即m只取2的幂,即m=2^k,k为正整数.

域K=$\mathbb{Q}$(ζ_m)中有n个自同构σ_i,对于所有$i \in \mathbb{Z}_m^*$,σ _i保持$\mathbb{Q}$中元素保持不变,将ζ_m映射为$\zeta _m^i$,标准映射$\sigma :K \to {K^{\mathbb{Z}_m^*}}$定义为

$\sigma (a) = {({\sigma _i}(a))_{i \in \mathbb{Z}_m^*}}.$

使用标准映射s可以定义K中元素的欧式范数:

· 对于a∈K,a的欧式范数定义为$||a|{|_2} = ||\sigma (a)|{|_2} = {\left( {\sum\nolimits_i {|{\sigma _i}(a){|^2}} } \right)^{1/2}}$;

· l_∞范数定义为max_i|σ_i(a)|;

迹函数$Tr = T{r_{K/\mathbb{Q}}}:K \to \mathbb{Q}$定义为自同构之和:$Tr(a) = \sum\nolimits_i {{\sigma _i}(a)} $.显然,对于任意a,b∈K和c∈$\mathbb{Q}$,迹函数满足Tr(a+b)=Tr(a)+Tr(b)和Tr(c⋅a)=c⋅Tr(a);

对于K中任意的分式理想I,它的对偶定义为

${I^ \vee } = \{ a \in K:Tr\left( {aI} \right) \subseteq \mathbb{Z}\} .$

很容易可以验证(I^∨)^∨=I,I^∨也是一个分式理想,且I^∨在σ映射下会变为I的对偶格.

下面介绍分圆环上的张量基,在构造本文体制时,它相比于幂基,生成陷门的效率更高,并且更适用于一些快速算法.定义如下:

定义2. R=$\mathbb{Z}$(ζ_m)的张量基p定义如下:

(1) 若m为某个素数的幂,那么p定义为幂基${(\zeta _m^j)_{j \in [\varphi (m)]}}$;

(2) 若m有素数幂分解$m = \prod\nolimits_l {{m_l}} $,定义p=⊗_lp_l,其中,p_l为R=$\mathbb{Z}$(ζ_m)的幂基.

2.3 RLWE问题

定义3(RLWE分布). 对于$s \in R_q^ \vee $(秘密)和${K_\mathbb{R}}$上的一个误差分布Ψ,那么${R_q} \times ({K_\mathbb{R}}/q{R^ \vee })$上的RLWE分布A_s,Ψ中的一个抽样生成方式如下:均匀随机地选择a←R_q,选择e←Ψ,输出(a,b=a⋅s+e mod qR^∨).

定义4(DRLWE假设). 无法以不可忽视的优势来区分以下两个分布:第1个是从A_s,Ψ中独立抽样,其中随机选择$s \leftarrow R_q^ \vee $;第2个是从${R_q} \times ({K_\mathbb{R}}/q{R^ \vee })$中均匀随机地取出同样数量的相互独立的抽样,记作DRLWE_q,Ψ假设.

在加密应用中,具有离散误差分布的RLWE问题通常更有用.我们可以自然地定义一个分布A_s,χ,其中,χ为R^∨上的离散误差分布,那么b就是$R_q^ \vee $上的元素.类似地,我们可以修改定义4,令DRLWE_q,χ是区分A_s,χ和均匀地从${R_q} \times R_q^ \vee $采样的问题.对于很多种类的离散误差分布,问题的离散形式的困难性是由问题的连续形式来产生的.下面的定理意味着:如果DRLWE_q,Ψ在l个抽样的情况下是难的,那么DRLWE_q,χ在同样数目的抽样下也是难的.其中,误差分布χ是${[p \cdot \Psi ]_{\omega + p{R^ \vee }}}$,p是一个与q互质的整数,[⋅]是任意一个有效的离散化到pR^∨的方法,w是$R_p^ \vee $上一个任意元素,可以随着不同的采样而变化.特别地,对于p=1,得到误差分布${[\Psi ]_{{R^ \vee }}}$.记DRLWE_{q, Ψ}在l个抽样的情况下为l-DRLWE_q,Ψ.

定理1. 令p和q是互质整数,[⋅]是任意一个将连续分布变为离散分布的方法,w是$R_p^ \vee $上的任意元素.如果DRLWE_q,Ψ问题对于给定某个数目l个抽样时是难的,那么DRLWE_q,Ψ的变体:秘密是抽样自$\chi = {[p\Psi ]_{\omega + p{R^ \vee }}}$在给定l-1个抽样时也是难的.

2.4 基于身份的全同态加密体制

全同态体制FHE分为4种算法:密钥生成KeyGen、加密Enc、解密Dec、同态运算Eval.前3种算法与一般的公钥加密体制类似,而同态运算则是对应代数结构上密文的运算,具体的定义见文献^[2].

IBE体制一般分为4种算法:参数选择Setup、私钥提取Extract、加密Enc、解密Dec.Setup算法中生成主公私钥对;Extract对于身份ID提取用户私;加解密与普通公钥体制类似,使用的密钥为用户公私钥对.若一个IBE体制同时也是FHE体制,即IBFHE体制,一般分为5种算法:参数选择Setup、私钥提取Extract、加密Enc、解密Dec、同态运算Eval.前4种算法与IBE相同,同态运算算法与FHE体制中的Eval算法相同.

3 任意分圆环上使用特征向量的全同态加密体制

本节首先给出LPR公钥体制,并在此基础上提出任意分圆环上近似特向量全同态加密体制;最后,结合SIMD技术进一步提升该体制的效率.

3.1 LPR公钥体制

该体制是针对文献^[14]公钥体制的变形,该体制可以转变为基于身份的加密体制.令R=$\mathbb{Z}$(ζ_m)为m次分圆数环,p,q为互质的整数,其中,使用p定义明文空间R_p,q为RLWE中的模数,令l≥2,Ψ是${K_\mathbb{R}}$上的连续高斯分布,D_R,r是R上离散高斯分布.体制共分为3个部分:LPR.KeyGen,LPR.Enc,LPR.Dec.

(1) 密钥生成算法LPR.KeyGen:令a₀=1,取e∈Ψ,s₀,…,s_l-1∈D_R,r,令si=(s₁,…,s_l-1),令私钥sk=s=(1,-si)∈R^l,在R_q上均匀随机取a₁,…,a_l-1,令$pk = A = \left( {{a_l} = \sum\nolimits_{i \in [l]} {{a_i}{s_i}} ,{a_1},...,{a_{l - 1}}} \right) \in {R^l}$为公钥,可以发现,A⋅s=s₀;

(2) 加密算法LPR.Enc(m∈R_p,pk):加密μ时,取${e_0} \leftarrow {\left[ {p\Psi } \right]_{p{R^ \vee }}},{e_1} \leftarrow {\left[ {p\Psi } \right]_{{t^{ - 1}}\mu + p{R^ \vee }}},{e_2},...,{e_l} \leftarrow {[p\Psi ]_{p{R^ \vee }}},$令e= (e₁,…,e_l)∈(R^∨)^l,得到密文$c = {e_0} \cdot A + e \in {(R_q^ \vee )^l}$;

(3) 解密算法LPR.Dec(c,sk):计算d=$\left\langle {c,s} \right\rangle $ mod qR^∨,输出明文μ=t⋅d mod pR.

正确性的讨论见文献^[14],关于安全性有如下定理:

定理3.1^[14]. 若r＞2n⋅q^1/l+2/(nl)且(l+1)-DRLWE_q,Ψ的是难的,LPR公钥体制具备IND-CPA安全性.

3.2 体制描述

选择模数q,令l′=$\left\lceil {\log q} \right\rceil $,N=l⋅l′,取$R_q^ \vee $的一组好基p=(p₁,…,p_n)(本文中的好基指这组基构成的矩阵的奇异值较小,如第2.2节中提到的张量基),首先定义本节中用到的几个函数:

· 对于$a \in {(R_q^ \vee )^l},BitDecomp(a) = ({a_{1,1}},...,{a_{1,l'}},...,{a_{l,1}},...,{a_{l,l'}}) \in {(R_q^ \vee )^N}$,其中,a_i,j是a_i二进制表示的第j个比特;

· 对于$b = ({b_{1,1}},...,{b_{1,l'}},...,{b_{l,1}},...,{b_{l,l'}}) \in {(R_q^ \vee )^N}$,定义以下函数:

$\begin{gathered} BitDecom{p^{ - 1}}(b) = \left( {\sum\nolimits_{i = 1}^{l'} {{2^{i - 1}} \cdot {b_{1,i}},...,} \sum\nolimits_{i = 1}^{l'} {{2^{i - 1}} \cdot {b_{l,i}}} } \right) \in {(R_q^ \vee )^l}; \hfill \\ Flatten(b) = BitDecomp(BitDecom{p^{ - 1}}(b)); \hfill \\ Powersof2(a) = ({a_0},2{a_0},...,{2^{l - 1}}{a_0},{a_1}) \in {(R_q^ \vee )^N}. \hfill \\ \end{gathered} $

(6)

若这些函数的自变量为矩阵,意为将矩阵的每一行看作向量进行函数调用.体制分为密钥生成算法AE.KeyGen、加密算法AE.Enc、解密算法AE.Dec、密文运算算法AE.Evaluate这4个部分.

(1) AE.KeyGen:首先令a₀=1,取e∈Ψ,s₀,…,s_l-1∈D_R,r,令si=(s₁,…,s_l-1),s=(1,-si)∈R^l,在R_q上均匀随机a₁,…,a_l,令$pk = A = \left( {{a_l} = \sum\nolimits_{i \in [l]} {{a_i}{s_i},{a_1},...,{a_{l - 1}}} } \right) \in {R^l}$为公钥,私钥sk=v←Powersof2(s)∈R^N;

(2) AE.Enc(μ′∈R_p,pk):先生成N个LPR公钥体制中0的密文,令矩阵C′的每一行分别是这些0的加密结果,则$C' \in {(R_q^ \vee )^{N \times l}}$,令密文矩阵为$C \leftarrow Flatten(\mu ' \cdot {I_N} + BitDecomp(C')) \in {(R_q^ \vee )^{N \times N}}$(I_N为N维单位矩阵);

(3) AE.Dec(C,sk):计算C⋅v=μ′⋅v+BitDecomp(C′)⋅v=μ′⋅v+C′⋅s,解密时只需一行即可,令C_i为C的第i行,计算y_i=$\left\langle {{C_i},v} \right\rangle $,输出μ′=y_i/v_i;

(4) AE.Evaluate(C₁,C₂):令密文矩阵C₁加密明文m₁,C₂加密明文m₂.令${C_1} \cdot v = {\mu _1} \cdot v + {e'_1},{C_2} \cdot v = {\mu _2} \cdot v + {e'_2}$,其中,e′和${e'_2}$为N个LPR公钥体制中加密0的密文与v相乘的结果(即N个e₀⋅s₀+$\left\langle {e,s} \right\rangle $,该结果模pR得到明文0).

同态加法为$({C_1} + {C_2}) \cdot v = ({\mu _1} + {\mu _2}) \cdot v + ({e'_1} + {e'_2})$;

同态乘法为$({C_1} \cdot {C_2}) \cdot v = {C_1} \cdot ({\mu _2} \cdot v + {e'_2}) = {\mu _2} \cdot ({\mu _1} \cdot v + {e'_1}) + {C_1} \cdot {e'_2} = {\mu _1} \cdot {\mu _2} \cdot v + {\mu _2} \cdot e' + {C_1} \cdot {e'_2} = {\mu _1} \cdot {\mu _2} \cdot v\bmod pR$.

3.3 AE体制正确性与安全性分析

· 正确性

解密算法输出为

$\begin{gathered} {y_i}/{v_i} = \langle {C_i},v\rangle /{v_i} \hfill \\ {\text{ }} = \langle (\mu ' \cdot {({I_N})_i} + BitDecomp({{C'}_i})),v\rangle /{v_i} \hfill \\ {\text{ }} = \mu ' \cdot {v_i}/{v_i} \hfill \\ {\text{ }} = \mu ', \hfill \\ \end{gathered} $

(7)

其中,(I_N)_i表示矩阵I_N的第i行,${C'_i}$表示C′的第i行.

由于C′的每一行都是加密0得到的加密结果,所以$\langle BitDecomp({C'_i}),v\rangle $的结果就是0.

· 关于体制的安全性有如下定理

定理2. 设系统参数n=n(λ),q=q(λ),L=L(λ)为安全参数λ的多项式,取错误分布x=x(λ)为环上高斯分布D_R,r,r＞2n⋅q^1/l+2/(nl),n≥2lgq,在DRLWE_q,c假设的前提下,AE体制是IND-CPA安全的.

证明:定理证明采用基于游戏序列的证明方法,用Adv_Game[A]来定义攻击者A在Game中的优势.

· Game 0

Game 0即标准的IND-CPA游戏:挑战者C调用密钥生成算法AE.KeyGen生成公钥pk,并将其交给攻击者A,A没有访问解密谕示的能力,因此选择挑战明文$\mu _0^*,\mu _1^* \in {R_q}$,C从中随机选择$\mu _b^*$,加密生成挑战密文c并将其交给攻击者A,A猜测c对应明文为m_b.攻击者A的优势记为

$Ad{v_{CPA}}[A] = |\Pr [A(pk,AE.Enc(pk,\mu _0^*))] - \Pr [A(pk,AE.Enc(pk,\mu _1^*))]|$

(1)

· Game 1

Game 1与Game 0的区别在于公钥的生成方式.Game 1的公钥pk直接从R^l中均匀随机取得.由文献^[14]推论7.5可知,公钥pk与R^l上的均匀分布的统计距离在2^-Ω(n)以内.即,A区分Game 0与Game 1的概率小于2^-Ω(n),因此:

$|Ad{v_{Game1}}\left[ A \right] - Ad{v_{CPA}}\left[ A \right]| ＜ {2^{ - \Omega \left( n \right)}}$

(2)

· Game 2

在Game 1的基础上,加密算法被修改,密文中的C′不再是0的密文,而是从${(R_q^ \vee )^{N \times l}}$均匀随机抽取.由文献^[14]引理8.1与DRLWE_q,c假设可知,修改前与修改后的C′是计算不可区分的.因此,A区分Game 1与Game 2的概率小于n的可忽略函数,记作negl(n),因此有:

$|Ad{v_{Game2}}\left[ A \right] - Ad{v_{Game1}}\left[ A \right]| \leqslant negl\left( n \right)$

(3)

· Game 3

在Game3中,C给出的挑战密文不再由加密算法生成,而是直接从${(R_q^ \vee )^{N \times N}}$生成.

由C=Flatten(μ′⋅I_N+BitDecomp(C′))知,BitDecomp^-1(C)=μ′⋅BitDecomp^-1(I_N)+C′.由于此前Game 2中C′已替换为${(R_q^ \vee )^{N \times l}}$上的随机值,因此,BitDecomp^-1(C)与${(R_q^ \vee )^{N \times l}}$上的随机分布计算不可区分,即,C与${(R_q^ \vee )^{N \times N}}$上的随机分布计算不可区分,故有:

$|Ad{v_{Game3}}\left[ A \right] - Ad{v_{Game2}}\left[ A \right]| \leqslant negl\left( n \right)$

(4)

至此,在Game 3中,挑战者所给出的公钥、密文都服从均匀分布,且与目标密文之间完全独立,因此,A在Game 3中能取得的优势为0,即:

$Ad{v_{Game3}}\left[ A \right] = 0$

(5)

结合公式(3.1)～公式(3.5),可得:

$Ad{{v}_{CPA}}\left[ A \right]{{2}^{-}}^{\Omega \left( n \right)}+2negl\left( n \right).$

因此,在DRLWE_q,c假设成立的情况下,Adv_CPA[A]可忽略,即,AE体制是IND-CPA的,安全性得证. □

3.4 SIMD技术

从文献^[5]的分析可以看出,SIMD技术实际是一种并行思想.目前,SIMD技术相继被应用到LWE体制和RLWE体制中,实现了两种SIMD全同态加密体制^{[21, 22]}.文献^[21]中,Gentry等人使用了包括SIMD技术在内的多种优化效率方法,极大地降低了计算复杂度.而基于该体制实现的AES加密算法实验^[23],证明该体制在一定程度上已可以应用于实际.

具体方法是:将整个明文空间R_p=R/pR(其中,R=$\mathbb{Z}$(x)/(φ_m(x)))分解为相同大小的子环,待加密的明文分别属于这些子环,然后将它们合成为R_p,对合成明文进行加密,即,相当于并行加密了子环上的所有明文.故,使用SIMD技术将大幅提升加解密的效率.但特殊分圆环不能进行分解,故,使用特殊分圆环无法使用SIMD技术.

在加密体制中,一般p都为质数,但$\left\langle p \right\rangle $一般不是质理想,接下来讨论对pR进行理想分解.令d≥0为满足p^d能整除m的最大整数,令h=ϕ(p^d),令a≥1为模m/p^d意义下p的乘法逆元,由文献^[6]知,φ_m(x)可分解为$\prod\nolimits_i {{{({f_i}(x))}^h}} $,那么pR可分解为$p_1^hp_2^h...p_e^h$,其中,e=ϕ(m)/(ha),p_i=$\left\langle {p,{f_i}(\zeta )} \right\rangle $是范数为p^a且两两不同的质理想.

第3.2节的IBFHE中,明文空间为R_p,故可将其如上分解,实现并行加密.若φ_m(x)可分解为k个首一不可约多项式,就可以同时加密k个明文.

3.5 效率分析

AE体制相比GSW体制,最大的区别就在于使用任意分圆环来代替特殊分圆环.由于特殊分圆环分布稀疏,所以在相同安全性条件下,使用任意分圆环的计算效率最高可达使用特殊分圆环的两倍,这是由于特殊分圆环的分圆多项式为φ_m(x)=2^m/2+1,举例来说,若m取256时并不能满足安全性条件,故只能取512.然而在256与512之间有许多可达到与512相同安全性的值,例如257,这样,任意分圆环与特殊分圆环的维数相差近乎两倍,那么环上运算的效率会相差至少两倍.任意分圆环的另一个优势在于,它可以利用中国剩余定理进行划分.因此,明文空间也可以分割为多份,就能支持SIMD技术.

表 1给出了两种体制在相同安全性条件下的效率分析对比.q为两种体制的模数,安全参数k取257,m为分圆多项式次数,n=j(m),那么GSW体制中n=512,AE体制中n=257.可以看出,两种体制的环维数相差接近两倍.令两种体制中公钥维数l=10.表中乘法与加法均指环上运算,但对于AE体制来说,环上运算所占用的空间较少.另外,AE体制相比基于LWE问题的体制,公钥尺寸也极大地缩小,以文献^[8]的BV体制为例,在格维数n=192的情况下,公钥尺寸将达到50.6MB.从表 3.1可看出,AE体制的公钥尺寸仅仅只有75.3KB.

4 任意分圆环上使用特征向量的基于身份公钥加密体制 4.1 任意环上的陷门生成

本节构造了任意环上的陷门,采用文献^[18]的思想,从整数环上的陷门转化为任意环上的陷门.此陷门在接下来构造基于身份的体制时使用.

对于矩阵$A \in R_q^{k \times l}$,定义:

· Λ^⊥(A)={y∈R^l:Ay=0 mod qR};

· ${\mathcal{L}^ \bot }(A) = \{ z \in {\mathbb{Z}^\ell }:Az = 0 \bmod {\text{ }}q\} $.

显然,Λ^⊥(A)和L^⊥(A)都是格.关于这两个格的基,有以下引理:

引理1. 令A,Λ^⊥(A),^Λ⊥(A)定义如下:若B是L^⊥(A)的任意一组$\mathbb{Z}$-基,b是R的任意一组$\mathbb{Z}$-基,那么B⊗b^T是Λ^⊥(A)的一组$\mathbb{Z}$-基.

给定格^Λ=L(B)的一组好基B={b_i},设Λ为n维,若使用空间H中一个点c来表示格陪集Λ+c,那么通过前像采样,可以得到Λ+c上的符合离散高斯分布的一系列点.采样的方法记作SampleR,具体流程如下:

1. 遍历i←1,…,n:

(a) 使用基B将c表示为$c = \sum\nolimits_i {{c_i}{b_i}} $,其中,c_i∈[0, 1];

(b) 随机从{c_i-1,c_i}中选取一个元素,并令其为f_i;

2. 输出$f = \sum\nolimits_i {{f_i}{b_i}} $.

接下来即可使用上述引理及采样方法进行陷门的构造,陷门构造过程共分为3步:

(1) 选择矩阵A为$R_q^{k \times l}$上均匀随机的矩阵,由引理4.1,选取L^⊥(A)的一组好基及R的一组好基(例如张量基),生成^Λ⊥(A)的好基T作为陷门;

(2) 陷门函数f_A定义为f_A(x)=Ax mod qR;

(3) 若给出$u \in R_q^l$,要计算向量x,首先计算满足等式A⋅t=0 mod qR的特解t;然后,利用陷门T进行前像采样,求得分布Λ-t上符合离散高斯分布的向量v,输出x=t+v.

4.2 基于身份的公钥加密体制

在基于身份的体制中,定义随机喻示$H:{\{ 0,1\} ^*} \to R_q^l$可将身份映射为LPR公钥,使用第4.1节中提出的陷门,则任意环上近似特征向量的基于身份加密体制IBAE如下:

(1) 参数生成IBAE.Setup:由陷门T生成陷门函数f_A,令主公钥为A,也即LPR体制中的公钥,主私钥为T;

(2) 私钥提取IBAE.Extract(A,T,id):令u=H(id),使用T进行前像采样,得到用户私钥$s \leftarrow f_A^{ - 1}(u)$;

(3) 加密算法IBAE.Enc(A,id,m):使用身份id加密明文m∈R₂,首先令$u = H(id) \in R_q^l$,输出密文:

$c = LPR.Enc\left( {m,u} \right);$

(4) 解密算法IBAE.Dec(s,c):执行LPR.Dec(c,s).

4.3 IBAE体制正确性与安全性分析

由第3.1节中关于LPR体制的正确性分析可知,IBAE体制的正确性同理.关于安全性有如下定理:

定理3. 若LPR体制具备IND-CPA安全性,并且其公钥在R^l上均匀地随机分布,那么IBAE体制在随机喻示模型下是IND-adaptive ID-CPA安全的.

证明:若存在一个针对IBAE体制的多项式时间攻击者A,在IND-ID-CPA攻击游戏中优势为ε(不可忽略),并且有Q_oragle次喻示访问权限条件,那么我们可以构造一个针对LPR体制的攻击者B,其在IND-CPA攻击游戏中优势为ε/Q_oragle.

攻击者B的输入LPR体制中公钥${u^*} \in R_q^l$,B首先随机选取i∈{1,…,Q_oragle},并模拟IBAE攻击游戏:

(1) 模拟随机喻示:对于A的第j次访问id_j,若j=i,那么保存三元组(id_j,u,^),并将u^*交给A;若j≠i,则调用LPR.KeyGen,生成公私钥对(u_j,s_j),保存三元组(id_j,u_j,s_j),并将u_j交给A;

(2) 模拟私钥提取喻示:若A以身份id访问私钥提取喻示,不失一般性地假设A已经用id访问过随机喻示,因此,B只需查询已保存的三元组(id,u,s),将s交给A,若s=⊥,那么输出一个随机值并终止;

(3) 模拟挑战密文:当A生成挑战明文$\mu _0^*,\mu _1^*$和挑战身份id^*时,不失一般性地假设A已经用id^*访问过随机喻示,若id^*≠id,即(id^*,u^*,⊥)并未保存过,那么输出一个随机值并终止;否则,B向LPR体制攻击游戏的挑战者发起挑战,得到挑战密文c,并将c^*交给A.

当A终止并输出结果时,B也输出同样的结果并终止.

在模拟过程中,B没有终止并输出结果的概率为1/Q_oragle(即id^*=id_i的概率),这时,B成功模拟出IBAE攻击游戏.根据假设可知,A在这种情况下攻击成功的优势为ε.故,B攻击IBAE体制的优势为ε/Q_oragle. □

4.4 基于身份的体制向基于身份的全同态体制的转化

本节介绍一种将基于RLWE的IBE体制(并且满足某些性质)转化为IBFHE的方法,该方法是文献^[20]中转化方法的关于环的变体.若一个IBE体制满足以下性质,那么都可以使用该方法进行转换:

(1) 对于身份id,令私钥为s_id∈R^l,对应密文为${c_{id}} \in {(R_q^ \vee )^l}$,那么s_id第1项为1;

(2) 若c_id加密了0,那么$\left\langle {{c_{id}},{s_{id}}} \right\rangle $=0 mod pR^∨;

(3) 0的加密结果与${(R_q^ \vee )^l}$上的均匀分布不可区分.

定理4. 若一个IBE体制E满足上述3条性质,那么该体制可以转化为一个IBFHE体制.

证明:IBFHE使用E的参数设置和密钥生成算法,并将E的主公钥加入AE中,令l′=$\left\lceil {logq} \right\rceil $,N=l⋅l′.为加密明文m∈{0,1},加密者使用E的加密算法生成N个0的加密结果,令${C'_{id}}$为N×l的矩阵,且它的每一行分别是这些密文,输出${C_{id}} = Flatten(\mu \cdot {I_N} + BitDecomp({C'_{id}})),$若s_id为身份id对应的私钥,那么解密者运行AE的解密算法来恢复m,同态运算的讨论与第3.2节中相同.

令v_id=Powersof2(s_id),那么由于性质(2),${C_{id}} \cdot {v_{id}} = \mu \cdot {v_{id}} + {C'_{id}} \cdot {s_{id}} = \mu \cdot {v_{id}}\bmod p{R^ \vee }$,故解密是正确的.若存在一个攻击者可以从上述IBFHE体制中区分${C'_{id}}$和${(R_q^ \vee )^{N \times l}}$上的均匀矩阵,则由性质(3),该攻击者也可以以不可忽略的优势解决DRLWE_q,c,即,证明了该体制安全性.故定理得证. □

显然,第4.2节提出的IBAE体制满足上面3条性质,故由上面定理,可将IBAE体制与第3.2节的AE体制结合得到一个IBFHE体制(IBAFHE体制).本体制以任意分圆环作为基本代数结构,因此与AE体制一样,IBAE体制也可实现SIMD技术.本节利用特征向量构造一个真正意义上的IBFHE体制,相比之下,Brakerski等人^[13]提出的体制在实际应用中必须借助公钥证书进行认证,而且还需要证书分发、管理.

4.5 效率分析与对比

与文献^[19]提出的IBFHE(GZF体制)相比,IBAFHE体制以RLWE问题作为基础,因此密文运算效率较高,加解密计算复杂度有很大降低,并且密文尺寸更短.表 2给出了IBAFHE与GZF体制在相同安全条件下的效率分析与对比.n为体制所使用格的维数(即$R_q^ \vee $或R_q对应的理想格维数),格维数都取192,GZF体制的公钥尺寸分为加密公钥和运算密钥两部分,而IBAFHE的公钥尺寸只包含加密公钥,故公钥尺寸大大缩小;另外,由于IBAFHE体制可使用SIMD技术,加解密效率可进一步提高,由第3.4节的分析,理想qR可分解为h=φ(q^d)个质理想,IBAFHE的加密时最多可以同时加密h份明文,故IBAFHE的加解密效率还可提高为h倍;GZF体制的私钥是整数上向量,IBAFHE的私钥是环上向量,故私钥尺寸有所增加.IBAFHE与GSW中基于身份的全同态体制相比,由于GSW中体制所使用的基础结构是特殊分圆环,因此要达到同等安全条件,GSW体制的维数至少要取256,公钥尺寸就会变大,相比本文体制大了33.3%.另外,GSW同样无法使用SIMD技术.

5 总结

在云计算的背景下,全同态加密有着广阔的应用前景,但效率低下的问题一直制约着全同态加密在实际中的应用.因此,本文先给出基本的公钥体制和一种陷门生成算法,然后针对全同态加密体制效率低下的问题,结合近似特征向量方法和SIMD技术,使用任意分圆环提出了一个IBFHE体制,相比已有的IBFHE体制,效率大大提升.