基于NTRU的全同态加密方案

一种NTRU格上基于身份全同态加密体制设计段然;顾纯祥;祝跃飞;郑永辉;陈莉【摘要】全同态加密可以用来解决云计算环境中的隐私保护问题,然而现有体制具有系统参数大、效率低的缺点.针对现有攻击技术,首先设计了一种高效的NTRU格上的基于身份公钥加密体制,无需借助额外的安全性假设,具有更高的安全性和更小的系统参数.之后,基于近似特征向量技术,构造了一种高效的全同态加密转化方式.通过将以上两种方法结合,给出了一种高效的基于身份全同态加密体制.和现有体制相比,除了不需要计算密钥、实现了真正意义上的基于身份特性以外,还减小了密钥、密文尺寸,提高了计算和传输效率.【期刊名称】《电子学报》【年(卷),期】2018(046)010【总页数】8页(P2410-2417)【关键词】全同态加密;基于身份加密;环上带错学习问题;NTRU格;近似特征向量【作者】段然;顾纯祥;祝跃飞;郑永辉;陈莉【作者单位】信息工程大学四院,河南郑州450002;数学工程与先进计算国家重点实验室,江苏无锡214125;信息工程大学四院,河南郑州450002;数学工程与先进计算国家重点实验室,江苏无锡214125;信息工程大学四院,河南郑州450002;信息工程大学四院,河南郑州450002;数学工程与先进计算国家重点实验室,江苏无锡214125;河南财经政法大学网络信息安全研究所,河南郑州450046【正文语种】中文【中图分类】TP309.71 引言全同态加密(FHE，Fully Homomorphic Encryption)是一种新型加密技术，除了满足一般公钥加密性质，还可以通过对密文进行运算操作，实现对相应明文的相应运算.该技术可以用于实现隐私保护，进行安全多方计算等.2009年，Gentry基于理想格上的困难问题给出了第一个全同态加密体制[1].在此以后，学术界又提出了基于不同代数结构的全同态体制[2～5]，对相关领域的研究也在不断发展[6～13]. 目前，全同态体制存在的一个较大的问题是密钥尺寸较大，从而在密钥管理上的开销较大，影响体制的效率.通过引入基于身份加密(IBE，Identity-Based Encryption)的理念，用户公钥可以通过身份标识信息计算获得，可以有效解决这一问题.目前基于身份的全同态体制(IBFHE，Identity-Based Fully Homomorphic Encryption)的构造方式主要分为两类：第一类以光焱等人在2014年提出的体制[14,15](记作GZF体制)为代表，体制在密文运算中需要引入运算密钥防止密文尺寸不断增大.该密钥须使用用户私钥产生，并非真正意义上的IBFHE体制，且这类体制的运算密钥尺寸较大.第二类以Gentry等人在2013年利用近似特征向量技术提出的体制[16](记作GSW体制)为代表，体制的最大特点是无需运算密钥，但体制的密文尺寸较大.NTRU算法由Hoffstein等人提出[17]，被认为具有与求解特定格上困难问题难度相当的安全性[18,19].2014年，Ducas等人提出了一种基于NTRU的IBE体制(记作DLP体制)[20]，具有较小的密文尺寸和较高的计算效率.但为了保证安全性，体制在进行加解密过程中使用了密钥封装技术，从而使密文不具有同态性，无法构造FHE体制.本文首先提出了一个高效的NTRU格上的IBE体制，与DLP体制相比，密钥、密文尺寸减小了52.13%，且安全性更高.之后，基于近似特征向量技术，本文构造了一种将IBE体制转化为IBFHE体制的方法，与GSW体制中的转化方式相比，密文尺寸减小了83.28%.通过将两种思路结合，本文给出了基于NTRU格的IBFHE 体制.与现有体制相比，密钥、密文尺寸显著减小.在随机谕示模型下，基于环上带错学习问题(RLWE，Learning With Errors over Rings)和NTRU问题困难性，体制在选择明文和适应性选择身份攻击下具有不可区分性(IND-ID-CPA安全).2 预备知识2.1 符号定义本文符号统一如下：,,,q分别表示整数集，有理数集，实数集，整数模q剩余类环.对于n次多项式f(x)，R表示多项式环[x]/f(x)，R′表示多项式环[x]/f(x)，Rq表示环q[x]/f(x).定义n维向量a的长度为其欧几里德范定义向量集S的长度表示从概率分布D中随机选取变量表示从集合A中随机均匀选取变量x.向量可表示为a=(a1,…,an)；多项式b∈Rq可表示为b=(b1,…,bn)，Rq上的多项式和上的向量可以通过系数对应的方式相互转化.矩阵C的第i行用ci表示，In表示n维单位矩阵.φ(·)表示欧拉函数.对于多项式b,c∈R，定义b*c=bcmod(xn+1).logn表示log2n.除了常用的计算复杂度符号以外，本文还定义了poly(·)：如果存在常数c使得f(n)=O(nc)，则f(n)可表示为poly(n).2.2 NTRU格NTRU格在密码学中具有广泛的应用，具有结构较为特殊和运算效率较高等特点. 定义1[21] 对于m维欧氏空间m，给定n个线性无关向量b1,b2,…,bn∈m，由这些向量作为格基生成的格Λ，记作L(b1,b2,…,bn)或L(B)，定义为对于格基B，定义B*为B的格拉姆施密特正交化矩阵.这两个矩阵满足其中对于格L(B)，将格Λ⊥(B)定义为Λ⊥(B)={e∈m|B·e=0modq}.定义2[22] 对于正整数n,q，令f,g,F,G∈R满足f*G-g*F=q.由f,g,F,G生成的NTRU格是指将如下矩阵的列向量作为格基生成的格其中M(·)是n×n维的反循环矩阵，如2.3 环上带错学习问题RLWE问题是一种格上困难问题，最早由Lyubashevsky等人于2010年提出.该问题的判定性问题记作DRLWE问题(Decisional-RLWE).对于正整数m，在中添加m次本原单位根ξm所得到的域扩张K=(ξm)称为m次分圆数域.令n=φ(m)，当m为2的方幂时，n=m/2，此时K上的整数环[ξm]≅[x]/(xn+1).定义3[14] 对于正整数n，令Λ∈n为n维格.对于n上的任意向量c及任意实数σ>0，定义ρσ,c(Λ)=∑x∈Λρσ,c(x)将格Λ上以c为中心，参数为σ的离散高斯分布DΛ,σ,c (·)表示为∀当c=0时，该分布简写为DΛ,σ ，也可称作n上的错误分布，记作χ.下面给出与RLWE问题相关的定义.定义4[18] 对于正整数n，q=poly(n)，“秘密值”s∈Rq，以及n上的误差分布χ，RLWE分布定义为在Rq×Rq上的满足(a,a·s+e)形式的概率分布As,χ，其中称为RLWE分布的一个实例.在给出l个实例的情况下求解s的问题称为l-RLWEq,n,χ问题.定义5[18] 对于正整数n，q=poly(n)，以及n上的误差分布χ，DRLWE q,n,χ 问题的目标是区分如下两个分布.分布1：输出(a,b)←As,χ∈Rq×Rq.分布2：输出如果存在在给出l个实例的情况下以不可忽略的优势求解DRLWE q,n,χ 问题的多项式时间算法，那么称l-DRLWE q,n,χ 问题是简单的；否则认为问题是困难的.如果该问题是困难的，那么称l-DRLWE q,n,χ 假设成立.Lyubashevsky等人在文献[18,23]中给出了从理想格上近似最短向量问题(Approx SVP，Approximate Shortest Vector Problem)的最坏情况到DRLWE问题一般情况的量子归约.2.4 离散高斯采样函数Lyubashevsky等人于2015年提出了一种高效的从离散高斯分布上采样的算法[22].定理1[22] 存在可以进行如下运算的多项式时间算法CGS：输入格基B={b1,…,bn}，中心c，以及高斯参数σ，输出从DΛ(B),σ,c 上采样的结果z.该算法的输出满足如下命题：命题1[24] 对于任意的ε<2-λ/(4n)，如果那么CGS算法的输出与分布DΛ(B),σ,c 的统计距离不超过2-λ.3 高效的NTRU上基于身份的公钥加密体制设计本节通过对Ducas等人提出的IBE体制[20]中的加解密算法进行修改，提出了参数更小、效率更高的基于NTRU体制的IBE体制.3.1 体制设计我们首先给出DLP体制的参数生成和私钥提取算法.定义x′∈R′满足M(x′)=M(x)T.参数生成算法DLP.Keygen(n,q).输入多项式环的次数n和模数q，输出主公钥h和主私钥B，以及哈希函数算法过程如下：步骤1 计算步骤2 从分布Dn,ρf,σc中采样f,g←Dn,ρf,σc，如果则重新进行采样；步骤3 使用扩展欧几里德算法，计算rf,rg∈R，Rf,Rg∈使得rf·f=Rfmod(xn+1)，rg·g=Rgmod(xn+1).如果GCD(Rf,Rg)≠1或GCD(Rf,q)≠1，则返回步骤2；步骤4 计算tf,tg∈使得tf·Rf+tg·Rg=1；步骤5 计算X=qtgrg，Y=-qtfrg，k=+0.5∈R，F=X-k*f，G=Y-k*g；步骤6 计算主公钥h=g*f-1modq，主私钥私钥提取算法DLP.Extract(B,id).输入主私钥B和用户身份id∈{0,1}*，输出用户私钥skid：首先检查输入id是否在存储列表中.如果存在，则返回与id对应的skid.否则，计算用户公钥t←H(id)，调用CGS算法采样(s1,s2)←(t,0)-CGS(B,(t,0))，此时s1,s2满足s1+s2*h=t.将s2作为用户私钥和id存储在列表中，然后输出s2.Ducas等人指出[20]，DLP.Extract(B,id)算法得到的(s1,s2)与的分布Dn,σ3是统计不可区分的.然后我们构造如下的IBE体制，记作NE体制.体制包含参数生成算法、私钥提取算法、加密算法和解密算法四个多项式时间算法.参数生成算法NE.Setup(n,q).输入多项式环的次数n和模数q，调用DLP.Keygen(n,q)算法输出主公钥h和主私钥B.私钥提取算法NE.Extract(B,id).输入主私钥B和用户身份id∈{0,1}*，调用DLP.Extract(B,id)算法得到用户私钥skid.加密算法NE.Enc(id,μ).算法输入用户身份id和明文μ∈R2，输出用户公钥t对μ加密的密文c：计算t←H(id).从{-1,0,1}n上均匀随机选取r,e1，从参数为σ的离散高斯分布χ上选取e2，从{0,1}n上均匀随机选取k，计算u=r*h+e1∈Rq，v=r*t+e2+⎣q/2」·k∈Rq.输出c=(u,v,μ⊕H′(k))∈Rq×Rq×R2.解密算法NE.Dec(skid,c)：算法输入用户私钥skid和明文μ对应的密文c=(u,v,w)，计算w′=v-u*skid，k=⎣2w′/q+0.5」，输出明文μ=w⊕H′(k).解密正确性：由于s1+s2*h=t，所以有v-u*s2=r*t+e2-(r*h+e1)*s2=⎣q/2」·k+(r*s1+e2-e1*s2)当w′的所有系数都在区间(-q/4,q/4)以内时，解密算法可以正确得到k，从而恢复明文.系统参数的具体取值将在3.3节进行分析.体制安全性：与DLP体制类似，体制的安全性有如下结论.命题2[18] 设系统参数n=poly(λ)，q=poly(λ)为安全参数λ的多项式，如果NTRU问题是困难的，1-DRLWEq,n,χ1和1-DRLWEq,n,χ2假设成立，且H′为安全级别不低于λ比特的抗碰撞哈希函数，那么NE体制在随机谕示模型下是IND-ID-CPA安全的.3.2 高效的不使用密钥封装技术的基于身份公钥加密体制我们在本小节中对体制的密钥、密文结构和加解密流程进行修改，以得到可以通过GSW方式转化为IBFHE体制的IBE体制(记作NE2体制).与DLP体制通过类似方式修改得到的体制(记作DLP2体制)相比，体制的参数更小，效率更高.NE2体制包含参数生成、私钥提取、加密和解密四个多项式时间算法.参数生成算法NE2.Setup(n,q).输入维数n和模数q，调用DLP.Keygen(n,q)算法输出主公钥h和主私钥B.私钥提取算法NE2.Extract(B,id).输入主私钥B和用户身份id∈{0,1}*，调用DLP.Keygen(n,q)算法得到(s1,s2)，用户私钥加密算法NE2.Enc(id,μ).算法输入用户身份id和要加密的明文信息μ∈R2，输出用户公钥t对μ加密的密文c：计算t←H(id).从参数为σ1的离散高斯分布χ1上选取r,e2，从参数为σ2的离散高斯分布χ2上选取e1，计算u=r*h+e1∈Rq，v=r*t+e2+⎣q/2」·μ∈Rq.输出解密算法NE2.Dec(skid,c).输入用户私钥skid和明文μ对应的密文c=(u,v)，计算w=<skid,c>，输出明文μ=⎣2w/q+0.5」.解密正确性与NE体制相同.我们通过如下定理证明体制的IND-ID-CPA安全性.定理3 设系统参数n=poly(λ),q=poly(λ)为安全参数λ的多项式，如果NTRU问题是困难的，1-DRLWEq,n,χ1，1-DRLWEq,n,χ2，1-DRLWEq,n,χ3假设均成立，那么NE2体制在随机谕示模型下是IND-ID-CPA安全的.证明根据NTRU问题困难性，主公钥h与上的均匀分布不可区分.如果攻击者可以破坏体制的IND-CPA安全性，那么攻击者就可以区分(h,t,u,v)和上的均匀分布.从私钥提取算法和加密算法的过程可以看出，区分(h,t)和上的均匀分布、(h,u)和上的均匀分布、(t,v)和上的均匀分布分别等价于求解1-DRLWEq,n,χ3、1-DRLWEq,n,χ1、1-DRLWEq,n,χ2问题.因此如果1-DRLWEq,n,χ1，1-DRLWEq,n,χ2，1-DRLWEq,n,χ3假设均成立，那么NE2体制是IND-CPA安全的.又因为NE2体制的参数生成算法、私钥提取算法、以及用户公钥的生成方法均与DLP体制相同，因此可以用与该体制相同的方法证明NE2体制在随机谕示模型下的IND-ID-CPA安全性.3.3 参数选取和效率对比在本小节中，我们对NE、NE2体制的进行参数选取.命题2、定理3给出了体制IND-ID-CPA安全的结论，下面我们结合目前对格上密码体制和格上困难问题求解算法的研究进展[25～27]，利用根式埃尔米特因子对体制的安全性进行刻画，确定体制的参数.与DLP体制相似，攻击本文体制的方法为攻击主公钥、用户私钥以及体制的IND-CPA安全性.除了对于NE2体制的IND-CPA安全性我们选用了效率更高的Lindner等人提出的解码攻击[28,29]外，其他攻击方法的分析与文献[20]中相同.对于解码攻击，令攻击的优势ε=2-32.安全参数是在使用基于“极限裁剪”技术的枚举算法[30]和“最近邻居搜索”技术的筛法[31]的BKZ2.0算法[32]和PBKZ算法[33]作为格基约减算法时的结果[34].令解密错误率不超过2-60.我们使用CPU为i7-4790(3.6GHz)、内存为16GB的台式计算机对基于NTL库和GMP库的算法的效率进行评估.这两个库可以对文中参数选取条件下的所有体制进行有效实现.我们用mpk,skid,ci,evk,enc,dec表示主公钥尺寸、用户私钥尺寸、密文尺寸、运算密钥尺寸、加密时间、解密时间.表1 IBE体制效率对比体制nlogqmpkskidciencdecλDLP5122311.5KB11.5KB23.5KB214μs173μs83NE25 6225.5KB5.5KB11.25KB98μs79μs91DLP210244141KB41KB82KB506μs412μs 107NE25124020KB20KB40KB237μs189μs111从表1可知，NE、NE2体制的密钥、密文尺寸、加解密时间比DLP、DLP2体制小52.13%～54.35%，安全性高4～8比特，因此在各方面均优于Ducas等人的体制.利用NE2体制，我们可以构造具有较小参数的IBFHE体制.下面给出利用Gentry等人的构造方式[16]对两种IBE体制进行转化所得的IBFHE体制进行参数对比(如表2所示).表2 基于不同IBE的IBFHE体制效率对比体制nlogqmpkskidciencdecDLP2409697388KB776KB147.02MB354ms132msNE 2204893186KB372KB67.57MB159ms61ms与基于DLP2的IBFHE体制相比，使用NE2体制优势明显.4 高效的基于近似特征向量技术的全同态加密转化方法设计Gentry等人于2013年提出了一种基于近似特征向量技术和LWE问题的IBFHE 体制[16]，体制的最大特点是在同态运算中无需使用运算密钥，但密文尺寸较大.本节通过对后一体制作适当修改，提出的一种使得密文尺寸更小的将IBE体制转化为IBFHE体制的方法，记作NF体制.该体制还可以通过与NE2体制结合进一步优化系统参数、提高效率.4.1 体制设计首先，我们定义如下几个函数.对于上的向量a,b，p为2的方幂，l=「logq/logp⎣，N=kl.将向量a的分量ai 以p进制形式表示为其中ai,j∈p，函数pDecompt(a)的结果为N维向量定义函数pDecompt-1(a′)=(∑pj·a0,j,…,∑pj·ak-1,j).定义函数pFlatten(a′)=pDecompt(pDecompt-1(a′)).定义函数powersofp(b)=(b1,pb1,…,pl-1b1,…,bk,pbk,…,pl-1bk).NF体制的具体描述如下.参数生成算法NF.Setup(n,q,d).输入维数n、模数q和最大计算深度d，调用IBE体制的参数生成算法生成并输出主公钥mpk和主私钥msk.私钥提取算法NF.Extract(msk,id).输入主私钥msk和用户身份id，调用IBE体制的私钥提取算法生成并输出用户私钥skid.加密算法NF.Enc(id,μ).输入用户身份id和明文μ∈{0,1}，通过如下操作输出密文C：调用IBE体制的加密算法得到N=2l个对0进行加密的密文，以这N个密文为列向量得到N×N的矩阵C′，输出密文C=pFlatten(μ·IN+pDecomp(C′)).解密算法NF.Dec(skid,C).输入用户私钥skid和明文μ对应的密文C，令sid=powerofp(skid)，输出明文μ=⎣2〈cN-1,sid〉/q+0.5」.同态加法算法NF.Add(C1,C2).输入密文C1,C2，输出同态加法后的密文C=pFlatten(C1+C2).同态乘法算法NF.Mult(C1,C2).输入密文C1,C2，输出同态加法后的密文C=pFlatten(C1·C2).4.2 正确性和安全性分析对于体制的正确性和安全性，与原转化方法相似，我们用如下定理刻画.定理4 如果所基于的IBE体制满足如下三条性质，则NF体制是IND-CPA安全的IBFHE体制：(1)对于用户id，用户私钥skid和加密所得的密文cid是上的向量，且skid的第二项为1；(2)正确性：如果c是使用id对应的公钥对0加密所得的密文，令E = n·((N-1)·p/2 + 21+logqmod logp) + 1，那么|〈c,skid〉|·4p(E+1)d<q；(3)安全性：对0进行加密所得的密文与上的均匀分布是不可区分的.证明通过加解密流程，有C·skid=μ·pDecompt-1(skid)+C′·skid.如果满足性质2，那么在进行d次同态运算后，|C′·skid|的所有分量均被限制在q/4p以内，通过对倒数第二列解密即可保证体制解密的正确性.如果存在破坏NF体制CPA安全的攻击者，则表明该攻击者可以区分c和上的均匀分布.所以，如果所基于的IBE体制满足性质3，那么NF体制具有IND-CPA的安全性.下面我们对DLP2体制和NE2体制是否满足定理4.1中的三条性质进行检验.根据密钥生成算法，体制的私钥满足性质1.对于加密0所得的密文c，只要令性质2就可以得到满足.因为这两个体制是IND-ID-CPA安全的，因此满足性质3.所以本转化方式可以将以上两个IBE体制转化为IND-ID-CPA安全的IBFHE体制.4.3 效率对比本小节首先利用GSW和NF这两种转化方法将DLP2体制转化为IBFHE体制，并进行效率对比，结果如表3所示.表3 基于不同转化方法的IBFHE效率对比方法nlogqlogpmpkskidciencdecGSW4096971388KB776KB147.02MB354ms132 msNF409613113524KB1.02MB24.58MB49ms23ms可以看出，与GSW中基于RLWE的转化方法相比，NF的密钥尺寸增加了35.05%，密文尺寸减小了83.28%，加解密时间减少了82.40%～86.11%.这是由于两种转化方式的主公钥尺寸均为nlogq比特，用户私钥尺寸均为2nlogq比特，GSW转化方式的密文尺寸为4nlog2q比特，NF转化方式的密文尺寸为4nl2logp比特.由于体制的密钥尺寸较小、密文尺寸较大，且在应用中密钥只需生成、传输一次，而全同态加密需要多个密文参与，因此总体上可以较大的提升传输效率、减小存储空间.此外，Gentry等人提出[16]，GSW转化方法可以通过将加密算法中的明文空间由μ∈{0,1}改为μ∈p而实现多比特加密，但会相应使得logq的值增大.与该方法相比，本文提出的转化方式可以在不增加系统参数的情况下实现多比特加密.这一改动会使得定理4.1中第二条性质里的E变为E = n·((N-1)·p/2 +21+logqmodlogp) + p，而在本文的参数选取条件下对logq的影响忽略不计.下面给出在加密13比特时两种转化方法的效率对比(如表4所示).可以看出，在加密13比特的条件下，与GSW转化方法相比，NF的密钥尺寸不变，密文尺寸减小了90.83%，加解密时间减少了90.33%～91.18%，优势更加明显.我们利用将NE体制与NF转化方式结合，得到NFE体制(如表5所示)，并与现有的IBFHE体制进行效率对比，主要包括：①光焱等人提出的基于带错学习问题的GZF体制[15]；②辛丹等人提出的基于RLWE问题的XGZ体制[35]；③Gentry等人提出的基于带错学习问题的GSW体制[16]；④通过MP环上陷门采样函数[36]将GSW体制转换为基于RLWE问题的体制；⑤康元基等人提出的基于任意分圆环技术和RLWE问题的KGZ体制[37]；⑥通过DLP基于NTRU格的陷门采样函数[20]将GSW体制转化为基于RLWE问题和NTRU问题的体制.对于NFE体制，取logp=11.表4 多比特加密条件下不同转化方式的IBFHE效率对比方法nlogqlogpmpkskidciencdecGSW409613113524KB1.02MB268.14MB557ms2 41msNF409613113524KB1.02MB24.58MB49ms23ms根据表5可以看出，表中的前四种体制由于运算密钥尺寸或密文尺寸过大，因此效率远低于NFE体制.与后两种体制相比，NFE体制的主公钥、用户私钥、密文尺寸以及加解密时间减少均有不同程度减小，且安全性不低于这两种体制.因此，在保证安全性相当的前提下，NFE体制的系统参数更小、效率更高.表5 IBFHE体制效率对比体制nlogqmpkskidcievkencdecλ(1)21467548.25GB46.05MB23.02MB162.74EB--120(2)20488226.27MB26.43MB26.27MB28.30TB--104(3)16595817.25GB10.64MB113.31TB0--120(4)1024576.35MB6.40MB40.98GB0--61(5)1708621.01MB1.11MB757.63MB01.84s678ms120(6)409697388KB776 KB147.02MB0354ms132ms127NFE2048122244KB488KB12.38MB025ms12 ms1275 总结对全同态加密体制而言，在不降低安全性的条件下减小密钥密文尺寸、提高效率可以有效提升体制的实用性.本文首先设计了一种高效的NTRU格上的IBE体制，无需借助额外的安全性假设，密钥、密文尺寸和运算时间与现有体制相比显著减小，且安全性也有所提高.之后，本文提出了一种基于近似特征向量技术的将环上IBE 体制转化为IBFHE体制的方法，与现有转化方法相比，密钥尺寸略有增加，密文尺寸大幅减小.通过将两种方法结合，可以进一步减小密文尺寸，且无需运算密钥. 参考文献【相关文献】[1] Gentry C.Fully homomorphic encryption using ideal lattices[A].Proceedings of the 41st Annual ACM Symposium on Theory of Computing[C].New york:ACM,2009.169-178. [2] Brakerski Z,Vaikuntanathan V.Fully homomorphic encryption from ring-LWE and security for key dependent messages[A].Proceedings of the 31st Annual International Cryptology Conference[C].Berlin:Springer,2011.505-524.[3] Brakerski Z,Vaikuntanathan V.Efficient fully homomorphic encryption from (standard) LWE[J].SIAM Journal on Computing,2014,43(2):831-871.[4] Brakerski Z,Gentry C,Vaikuntanathan V.(Leveled) Fully homomorphic encryption without bootstrapping[J].ACM Transactions on Computation Theory,2011,18(3):169-178.[5] 汤殿华,祝世雄,王林,等.基于RLWE的全同态加密方案[J].通信学报,2014,35(1):173-182. TANG DH,ZHU SX,WANG L,et al.Fully homomorphic encryption scheme fromRLWE[J].Journal of Communications,2014,35(1):173-182.(in Chinese)[6] Zhang P,Yu JP,Wang T.A homomorphic aggregate signature scheme based onlattice[J].Chinese Journal of Electronics,2012,21(4):701-704.[7] Gentry C,Groth J,Ishai Y,et ing fully homomorphic hybrid encryption to minimize non-interative zero-knowledge proof[J].Journal of Cryptology,2015,28(4):820-843. [8] Ducas L,Micciancio D.FHEW:Bootstrapping homomorphic encryption in less than a second[A].Proceeding of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C].Berlin:Springer,2015.617-640.[9] Gorbunov S,Vaikuntanathan V,Wichs D.Leveled fully homomorphic signatures from standard lattices[A].Proceedings of the 47th Annual ACM on Symposium on Theory of Computing[C].New york:ACM,2015.469-477.[10] Peikert C,Shiehian S.Multi-key FHE from LWE,revisited[A].Proceedings of the 13th IACR Theory of Cryptography Conference[C].Berlin:Springer,2016.217-238.[11] Benhamouda F,Lepoint T,Mathieu C,et al.Optimization of bootstrapping incircuits[A].Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms[C].New york:ACM,2017.2423-2433.[12] 陈振华,李顺东,王道顺,等.集合成员关系的安全多方计算及其应用[J].电子学报,2017,45(5):1109-1116.CHEN ZH,LI SD,WANG DS,et al.Secure multiparty computation of set membership and its applications[J].Acta Electronica Sinica,2017,45(5):1109-1116.(in Chinese)[13] Chen H,Hu YP,Lian ZZ.Properties of SV-style homomorphic encryption and their application[J].Chinese Journal of Electronics,2017,26(5):926-932.[14] Regev O.On lattices,learning with errors,random linear codes,andcryptography[J].Journal of the ACM,2009,56(6):34.[15] 光焱,祝跃飞,费金龙,等.利用容错学习问题构造基于身份的全同态加密体制[J].通信学报,2014,35(2):111-117.Guang Y,Zhu YF,Fei JL,et al.Identity-based fully homomorphic encryption from learning with error problem[J].Journal of Communications,2014,35(2):111-117.(in Chinese) [16] Gentry C,Sahai A,Waters B.Homomorphic encryption from learning witherrors:Conceptually-simpler,asymptotically-faster,attribute-based[A].Proceedings of the 33rd Annual International Cryptology Conference[C].Berlin:Springer,2013.75-92.[17] Hoffstein J,Pipher J,Silverman JH.NTRU:A ring-based public keycryptosystem[A].Proceeding of the 3rd International Algorithmic Number Theory Symposium[C].Berlin:Springer,1998.267-288.[18] Lyubashevsky V,Peikert C,Regev O.On ideal lattices and learning with errors over rings[J].Journal of the ACM,2013,60(6):43.[19] Stehlé D,Steinfeld R.Making NTRU as secure as worst-case problems over ideal lattices[A].Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C].Berlin:Springer,2011.27-47.[20] Ducas L,Lyubashevsky V,Prest T.Efficient identity-based encryption over NTRU lattices[A].Proceedings of the 20th Annual International Conference on the Theory and Application of Cryptology and Information Security[C].Berlin:Springer,2014.22-41. [21] Peikert C.A decade of lattice cryptography[J].Foundations and Trends in Theoretical Computer Science,2016,10(4):283-424.[22] Lyubashevsky V,Prest T.Quadratic time,linear space algorithms for gram-schmidt orthogonalization and gaussian sampling in structured lattices[A].Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C].Berlin:Springer,2015.789-815.[23] Lyubashevsky V,Peikert C,Regev O.A toolkit for ring-LWEcryptography[A].Proceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques[C].Berlin:Springer,2013.35-54.[24] Ducas L,Nguyen PQ.Faster gaussian lattice sampling using lazy floating-point arithmetic[A].Proceedings of the 18th Annual International Conference on the Theory and Application of Cryptology and Information Security[C].Berlin:Springer,2012.415-432. [25] Kirchner P,Fouque PA.An improved BKW algorithm for LWE with applications to cryptography and lattices[A].Proceedings of the 35th Annual International Cryptology Conference[C].Berlin:Springer,2015.43-62.[26] Lepoint T,Naehrig M.A comparison of the homomorphic encryption schemes FV,and YASHE[A].Proceedings of the 7th International Conference on Cryptology inAfrica[C].Berlin:Springer,2014.318-335.[27] Gama N,Nguyen PQ.Predicting lattice reduction[A].Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C].Berlin:Springer,2008.31-51.[28] Micciancio D,Regev ttice-Based Cryptography[M].Berlin:Springer,2011.713-715.[29] Lindner R,Peikert C.Better key sizes (and attacks) for LWE-basedencryption[A].Proceedings of the 11th International Conference on Topics in Cryptology[C].Berlin:Springer,2011.319-339.[30] Gama N,Nguyen PQ,Regev ttice enumeration using extremepruning[A].Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C].Berlin:Springer,2010.257-278.[31] Becker A,Ducas L,Gama N,et al.New directions in nearest neighbor searching with applications to lattice sieving[A].Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms[C].New york:ACM,2016.10-24.[32] Chen Y,Nguyen PQ.BKZ 2.0:Better lattice security estimates[A].Proceeding of the 17th International Conference on the Theory and Application of Cryptology and Information Security[C].Berlin:Springer,2011.1-20.[33] Aono Y,Wang YT,Hayashi T,et al.Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator[A].Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques[C].Berlin:Springer,2016.789-819.[34] Albrecht MR,Player R,Scott S.On the concrete hardness of learning witherrors[J].Journal of Mathematical Cryptology,2015,9(3):169-203.[35] 辛丹,顾纯祥,郑永辉,等.利用 RLWE 构造基于身份的全同态加密体制[J].电子学报,2016,44(12):2887-2893.XIN D,GU CX,ZHENG YH,et al.Identity-based fully homomorphic encryption from ring learning with errors problem[J].Acta Electronica Sinica,2016,44(12):2887-2893.(in Chinese) [36] Micciancio D,Peikert C.Trapdoors forlattices:Simpler,tighter,faster,smaller[A].Proceedings of the 31th Annual International Conference on the Theory and Applications of CryptographicTechniques[C].Berlin:Springer,2012.700-718.[37] 康元基,顾纯祥,郑永辉,等.利用特征向量构造基于身份的全同态加密体制[J].软件学报,2016,27(6):1487-1497.KANG YJ,GU CX,ZHENG YH,et al.Identity-based fully homomorphic encryption from eigenvector[J].Journal of Software,2016,27(6):1487-1497.(in Chinese)。

收稿日期：２０２０ ０７ １８；修回日期：２０２０ ０９ ０５ 基金项目：国家自然基金资助项目（６２０６２００９）；广西科技重大专项资助项目（ＡＡ１７２０４０５８ １７）；广西科技重大专项资助项目（桂科ＡＡ１８１１８０４７ ７） 作者简介：秦小月（１９９７ ），女，广西北海人，硕士研究生，主要研究方向为同态加密；黄汝维（１９７８ ），女（通信作者），广西岑溪人，副教授，主要研究方向为密码学（ｒｕｗｅｉｈ＠ｇｘｕ．ｅｄｕ．ｃｎ）．ＮＴＲＵ体制的全同态加密研究秦小月，黄汝维（广西大学计算机与电子信息学院，南宁５３０００４）摘　要：ＮＴＲＵ体制结构简单、解密速度快、多密钥处理自然，在后量子密码算法中备受关注，因此对ＮＴＲＵ体制的相关研究内容进行综述。

首先介绍了ＮＴＲＵ的研究发展和体制概论分析了解密失败的原因，并总结了基于ＮＴＲＵ体制的关键技术；其次给出了五种基于ＮＴＲＵ体制的全同态加密方案的分析比较，并总结了几种通用的优化方法；最后指出基于ＮＴＲＵ的加密方案待解决的关键问题，指明未来的研究方向，为研究ＮＴＲＵ体制的人员提供参考。

关键词：ＮＴＲＵ体制；全同态加密；解密失败中图分类号：ＴＰ３０９ 文献标志码：Ａ 文章编号：１００１ ３６９５（２０２１）０６ ００３ １６１９ ０７ｄｏｉ：１０．１９７３４／ｊ．ｉｓｓｎ．１００１ ３６９５．２０２０．０７．０２１３ＲｅｓｅａｒｃｈｏｎｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｏｆＮＴＲＵＱｉｎＸｉａｏｙｕｅ，ＨｕａｎｇＲｕｗｅｉ（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒ，Ｅｌｅｃｔｒｏｎｉｃｓ＆Ｉｎｆｏｒｍａｔｉｏｎ，ＧｕａｎｇｘｉＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｎｉｎｇ５３０００４，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＴｈｅＮＴＲＵｓｙｓｔｅｍ，ｗｉｔｈｉｔｓｓｉｍｐｌｅｓｔｒｕｃｔｕｒｅ，ｆａｓｔｄｅｃｒｙｐｔｉｏｎｓｐｅｅｄａｎｄｎａｔｕｒａｌｍｕｌｔｉ ｋｅｙｐｒｏｃｅｓｓｉｎｇ，ｈａｓａｔｔｒａｃｔｅｄｍｕｃｈａｔｔｅｎｔｉｏｎｉｎｐｏｓｔ ｑｕａｎｔｕｍｃｒｙｐｔｏｇｒａｐｈｉｃａｌｇｏｒｉｔｈｍｓ，ｓｏｔｈｉｓｐａｐｅｒｒｅｖｉｅｗｅｄｔｈｅｒｅｓｅａｒｃｈｒｅｌａｔｅｄｔｏｔｈｅＮＴＲＵｓｙｓｔｅｍ．Ｆｉｒｓｔｌｙ，ｉｔｉｎｔｒｏｄｕｃｅｄｔｈｅｒｅｓｅａｒｃｈａｎｄｄｅｖｅｌｏｐｍｅｎｔｏｆＮＴＲＵ，ｓｙｓｔｅｍｉｎｔｒｏｄｕｃｔｉｏｎ，ａｎａｌｙｚｅｄｔｈｅｒｅａｓｏｎｓｆｏｒｄｅｃｒｙｐｔｉｏｎｆａｉｌｕｒｅ，ａｎｄｓｕｍｍａｒｉｚｅｄｔｈｅｋｅｙｔｅｃｈｎｏｌｏｇｉｅｓｂａｓｅｄｏｎＮＴＲＵｓｙｓｔｅｍ．Ｓｅｃｏｎｄｌｙ，ｉｔｇａｖｅｔｈｅａｎａｌｙｓｉｓａｎｄｃｏｍｐａｒｉｓｏｎｏｆｆｉｖｅｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｓｃｈｅｍｅｓｂａｓｅｄｏｎＮＴＲＵｓｙｓｔｅｍ，ａｎｄｓｕｍｍａｒｉｚｅｄｓｅｖｅｒａｌｇｅｎｅｒａｌｏｐｔｉｍｉｚａｔｉｏｎｍｅｔｈｏｄｓ．Ｆｉｎａｌｌｙ，ｉｔｐｏｉｎｔｅｄｏｕｔｔｈｅｋｅｙｐｒｏｂｌｅｍｓｔｏｂｅｓｏｌｖｅｄｂｙＮＴＲＵ ｂａｓｅｄｅｎｃｒｙｐｔｉｏｎｓｃｈｅｍｅｓ，ｉｎｄｉｃａｔｅｓｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎ，ａｎｄｐｒｏｖｉｄｅｓｒｅｆｅｒｅｎｃｅｆｏｒｔｈｏｓｅｗｈｏｓｔｕｄｙＮＴＲＵｓｙｓｔｅｍ．Ｋｅｙｗｏｒｄｓ：ＮＴＲＵｓｙｓｔｅｍ；ｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎ；ｄｅｃｒｙｐｔｉｏｎｆａｉｌｕｒｅ０　引言同态加密概念在１９７８年首次被提出，源于隐私同态，从诞生到现在已有４０多年，但未有统一的划分标准，按照全同态的发展阶段以及支持密文运算的情况可将其分为部分同态加密、类同态加密以及全同态加密，其中全同态加密可以实现任意次密文的加、乘同态运算。

NTRU格上高效的基于身份的全同态加密体制段然;顾纯祥;祝跃飞;郑永辉;陈莉【期刊名称】《通信学报》【年(卷),期】2017(038)001【摘要】全同态加密是目前解决云计算网络数据隐私保护问题的最佳方案,但目前的体制的公钥尺寸普遍较大.首先,通过引入Kullback-Leibler散度的概念,构造一种NTRU格上的基于身份公钥的加密体制,参数分析表明体制具有较小的密钥和密文尺寸,实验数据表明体制具有较高的加解密效率.其次,利用近似特征向量技术,给出一种方法,将基于身份的公钥加密体制转换为基于身份的全同态加密体制,可以进一步减小密文尺寸.和现有体制相比,除了不需要计算密钥,实现真正意义上的基于身份特性以外,还减小了密钥和密文尺寸,提高了计算和传输效率.%Fully homomorphic encryption is the best solution for solving privacy concerns for data over cloud so far, while large public key size is a general shortcoming for existing schemes. First, by introducing the concept of Kull-back-Leibler divergence, an identity-based public key scheme over NTRU lattice with modified ciphertext form was proposed. Analysis on parameter setting showed its small key size and ciphertext size, and experiments revealed its high computational efficiency. Second, with the idea of approximate eigenvector, an improved method to convert the scheme into an identity-based fully homomorphic encryption one was put forward to further reduce ciphertext size. Compared with existing schemes, the converted scheme not only abandons evaluation keys to make it fully identity-based,but also has smaller keys and ciphertext, which results in higher computational and transmission efficiency.【总页数】10页(P66-75)【作者】段然;顾纯祥;祝跃飞;郑永辉;陈莉【作者单位】信息工程大学四院,河南郑州 450002;数学工程与先进计算国家重点实验室,江苏无锡 214125;信息工程大学四院,河南郑州 450002;数学工程与先进计算国家重点实验室,江苏无锡 214125;信息工程大学四院,河南郑州 450002;信息工程大学四院,河南郑州 450002;数学工程与先进计算国家重点实验室,江苏无锡214125;河南财经政法大学网络信息安全研究所,河南郑州 450046【正文语种】中文【中图分类】TP309.7【相关文献】1.利用RLWE构造基于身份的全同态加密体制 [J], 辛丹;顾纯祥;郑永辉;光焱;康元基2.新的格上基于身份的全同态加密方案 [J], 汤永利;胡明星;刘琨;叶青;闫玺玺3.利用特征向量构造基于身份的全同态加密体制 [J], 康元基;顾纯祥;郑永辉;光焱4.一种NTRU格上基于身份全同态加密体制设计 [J], 段然;顾纯祥;祝跃飞;郑永辉;陈莉5.NTRU格上高效的身份基线性同态签名方案 [J], 张建航; 曹泽阳; 徐庆征; 宋晓峰因版权原因，仅展示原文概要，查看原文内容请购买。

基于NTRU的全同态加密方案李子臣;张卷美;杨亚涛;张峰娟【摘要】本文提出一种基于公钥密码体制(Number Theory ResearchUnit,NTRU)选择明文攻击(Chosen Plaintext Attack,CPA)可证明安全的全同态加密方案.首先,对NTRU的密钥生成算法进行改进,通过格上的高斯抽象算法生成密钥对,避免了有效的格攻击,同时,没有改变密钥的分布.然后,基于改进的NTRU加密算法,利用Flattening技术,构造了一个全同态加密体制,并在标准模型下证明方案是选择明文攻击不可区分性IND-CPA安全的.%A fully homomorphic encrgption scheme was presented based on number theory research unit (NTRU),which is provable security about indistinguishable chosen plaintext attack (IND-CPA).Firstly,to avoid the effective lattice attacks,we modified the key generation algorithm of NTRU by Gaussian abstraction algorithm of lattices,and the distribution of the key is not changed.Then,we proposed a new homomorphic encrypfion scheme based on the improved NTRU encryption algorithm by using the Flattening technique.Its IND-CPA security was proved strictly under the standard model.【期刊名称】《电子学报》【年(卷),期】2018(046)004【总页数】7页(P938-944)【关键词】全同态加密;公钥密码体制NTRU;高斯抽样算法;可证明安全【作者】李子臣;张卷美;杨亚涛;张峰娟【作者单位】北京印刷学院,北京102600;北京电子科技学院,北京100070;北京电子科技学院,北京100070;西安电子科技大学通信工程学院,陕西西安710071;北京电子科技学院,北京100070;西安电子科技大学通信工程学院,陕西西安710071【正文语种】中文【中图分类】TP309.71 引言全同态加密允许对密文进行任意的运算，运算后的结果解密后等价于对明文进行相应计算的结果.随着互联网技术的日趋成熟和应用的广泛普及，用户的个人信息的隐私性也越来越多地得到重视.而全同态加密正是迎合了这一需求，全同态加密在云计算、密文检索、安全多方计算等方面都有着很重要的应用，因此，全同态加密成为近些年密码学家们的研究热点.早在1978年，Rivest等提出了全同态加密的概念[1].自从全同态加密的概念提出之后，构造全同态加密体制一直是一个公开的难题.密码学家们提出了很多同态加密体制，但它们都只具有单一的同态性，例如，ElGamal加密体制[2]、Goldwasser-Micali加密体制[3]、Paillier加密体制[4]都具有加法同态特性，RSA加密体制[5]具有乘法同态特性.直到2009年，Gentry提出了第一个全同态加密体制[6]，开启了全同态密码研究的先河.Gentry的体制是基于理想格，是具有开创性的奠基之作，但是，体制的效率较低，同时实现还较困难.所以，在第一个全同态加密方案提出之后，许多新的全同态加密方案的构造致力于向实际实现上靠近，并且基于更少的困难性假设.例如，基于整数的全同态加密方案[7]，基于LWE(Learning With Errors)困难问题的全同态方案[8]以及它的一系列改进方案[9,10]，等.在Brakerski，Gentry等提出的基于LWE的BGV方案[11]中，描述了一种新的约减密文噪音的方法“模交换”，使得全同态加密方案不再使用Gentry原始框架中的Bootstrapping方法，而Bootstrapping方法正是Gentry的全同态加密方案效率低下的症结所在.2013年，IBM研究中心发布了一个开源代码库HElib[12]，该库实现的是BGV方案.文献[13]提出一种基于同态加密的高效多方保密计算.文献[14]提出一种基于身份的同态加密方案，方案的安全性基于RLWE困难问题.文献[15]提出的全同态加密方案，降低了密文的扩张率. NTRU公钥加密体制是后量子加密算法中的典型代表[16]，是一个基于多项式环的密码体制.NTRU的安全性可以规约为格上的“近似最近向量问题”，可以抵抗已知的量子攻击.目前为止，并没有任何理由说明NTRU加密体制是不安全的[17].NTRU加密体制整个过程只包括小整数的加法、乘法以及模运算等线性运算，因此，算法的执行速度较快，被认为是公钥加密体制中最快的算法，也是比较容易实现的算法.最近，Lopez等提出基于NTRU的全同态加密方案[18]，但在密钥生成过程存在格攻击的安全问题，方案的安全性没有严格证明.本文在此基础上，在密钥生成部分，通过格上的高斯抽样算法生成密钥对，有效避免格攻击，并且不改变密钥的分布.在加密算法部分，把明文空间由原来的2扩展至p.利用Flattening技术[19]，构造一个全同态加密体制，在标准模型下严格地证明了该体制满足IND-CPA安全.2 相关定义及符号表示2.1 相关定义定义1 格上的高斯函数对于任意的s>0，定义n上的高斯函数，以c为中心，参数为s：∀(1)当下标s和c缺省时，s和c分别看做是1和0.对于任意的c∈n，实数s>0，n维格Λ，Λ的秩为k≤n，定义Λ上的离散高斯分布如下：∀(2)定义2 整数上的高斯抽样算法整数可以看做一维格，令在输入(s,c)和安全参数n的基础上，随机均匀地选择一个整数x←Z=∩[c-s·t,c+s·t]，那么，称以概率ρs(x-c)输出x.定义3[20] 格上的高斯抽样算法算法输入为n维基B∈n×k，基的秩为k，一个足够大的高斯参数s，一个中心c∈n，span(b1,…,bk-1)表示由b1,…,bk-1所张成的空间，输出为一个从DL(B),s,c中的一个样本.过程如下：(1)如果k=0，返回0.(2)计算即bk与span(b1,…,bk-1)正交的非零向量.(3)计算t，即c在span(B)上的映射，计算标量值(4)使用定义2中的针对的高斯抽样算法，选择一个整数(5)输出zbk+SampleD(B′,s,t-zbk)，其中，B′=[b1,…,bk-1].详细内容可参考文献[20].定义4[21] RLWE对于安全参数λ，令f(x)=xd+1，其中，d是2的幂次.令q≥2，并且是一个整数.令R=[x]/(f(x))，Rq=R/qR，χ=χ(λ)是R上的一个分布.RLWEd,q,χ问题是指区分以下两个分布：(1)从中均匀取样(ai,bi).(2)首先，均匀地从Rq中取样s，即s←Rq，然后均匀取样ai←q，从χ中取样ei，令bi=ai·s+ei.RLWEd,q,χ假设是指RLWEd,q,χ问题是不可行的.定义5 B-界多项式一个多项式e∈R是B-界的，如果满足定义6 B-界分布R上的一组分布{χn}n∈N是B-界的，如果从χn中选取的所有多项式e满足也就是说，B-界分布产生B-界多项式.定义7 IND-CPA安全定义一个敌手与挑战者之间的游戏，分为以下几个阶段.初始化阶段：挑战者运行加密体制的密钥生成算法，将生成的公钥交给敌手.预言机访问阶段：敌手选择明文，询问加密预言机，在得到密文应答之后，敌手可以多次分阶段提交选择的明文，并得到相对应于不同明文的密文.挑战阶段：敌手选取两个明文m0和m1，把这两个明文发送给挑战者，挑战者选取b∈{0,1}，并把挑战密文c=Encpk(mb)发送给敌手.猜测阶段：敌手试图猜测挑战密文所对应的b′，当b′=b时，认为敌手在攻击游戏中获胜.如果对于任意一个多项式时间的敌手A，在游戏中获胜的概率AdvIND-CPA(A)满足(3)其中，negl是可以忽略，λ是方案的安全参数.则称该体制是IND—CPA安全的.2.2 参数的表示及选取对于安全参数λ，方案的参数选取如下：整数n=n(λ).p=p(λ)，q=q(λ).n次多项式φ(x)=φλ(x).环R=q[x]/〈φ(x)〉上的一个B(λ)-界的误差分布χ=χ(λ).对于R中的元素a(x)=a0+a1x+…+an-1xn-1，它的l∞范数表示为多项式a(x)的系数ai∈{-⎣q/2」,…,⎣q/2」}，符号⎣」表示向下取整.3 NTRU加密体制3.1 NTRU加密体制[16]密钥生成KeyGen：在多项式环R=Z[x]/(xN-1)中，随机选取两个多项式f,g，次数均为N-1，系数为整数.p,q是整数，也不需要是素数，满足gcd(p,q)=1，q比p大.多项式f满足模p和模q都有逆，分别记为Fp,Fq，即Fp*f ≡ 1(modp)(4)Fq*f ≡ 1(modq)(5)计算h=Fq*g(modq)，上述式子中的modp，modq是指多项式的系数分别是区间和中的整数.那么，公钥pk=h，私钥sk=(f,Fp).加密Enc：m表示为多项式，次数为N-1，系数为整数.随机选取一个多项式φ，次数为N-1，系数为整数.c=pφ*h+m(modq)(6)解密Dec：首先计算a=f*c(modq)，其中a的系数属于集合然后计算m=Fp*a(modp).3.2 改进的NTRU加密体制密钥生成KeyGen(1λ)：λ为安全参数.选择一个足够大的标准差σ，使得f可以表示成如下形式：f=p·f ′+1，其中，f ′为从离散高斯分布Dn,σ中取样一个多项式，即f ≡ 1(modp)，从而使得解密过程更加高效.输入：其中，是Rq中可逆元素的集合，Rq=R/qR=Zq[x]/Φ.输出：一对密钥具体生成过程如下：(1)从离散高斯分布Dn,σ中取样f ′，令f=p·f ′+1，如果fmodq∉重新取样.当维数n取得很大的整数时，f ′是项数为n的多项式，f也是项数为n的多项式，Rq中模q可逆的多项式的概率很大，因此，满足条件的f的个数很多，保证了f 可以生成，并且是安全的.(2)从离散高斯分布Dn,σ中取样g，如果gmodq∉重新取样.(3)返回私钥sk=f，公钥Enc(pk,m)：明文空间为p，所有的计算都是在环R=q[x]/〈φ(x)〉上进行的，即模q和模φ(x)运算.输出密文c=hs+pe+m，其中，s和e都是从χ中抽样选取的多项式，且c∈R. Dec(sk,c)：m=fc(modp)(7)下面进行正确性分析：=f(hs+pe+m)=pgs+fpe+fm=p(gs+fe)+fm=fm(modp)(8)由密钥生成算法可知：f ≡ 1(modp)，正确性得证.4 全同态加密体制首先介绍文献[19]中的几个函数和Flattening技术.一个向量a=(a0,…,ak-1)分解成它的比特表示如下：BitDecomp(a)=(a0,0,…,a0,l-1,…,ak-1,0,…,ak-1,l-1)反之，我们也可从比特表示中恢复出这个向量，如下：BitDecomp-1(a)=(∑2ja0,j,…,∑2jak-1,j)(9)Flatten(a)=BitDecomp(BitDecomp-1(a))(10)然后，基于改进后的NTRU加密体制构造全同态加密方案，方案具体如下.密钥生成算法KeyGen：与改进的NTRU加密方案的密钥生成算法相同.即，通过格上的高斯抽样算法得到公私钥对，这样可以避免有效的格攻击，同时不会改变密钥的分布空间[22].加密算法Enc：首先，选取一个明文m∈p，然后利用改进后的NTRU加密体制的加密算法对0进行加密，得到一个长度为l=logq的密文向量c，如下：c=(cl-1,cl-2,…,c0)其中，ci是由改进的NTRU的加密体制对0加密得到的密文.即，ci=hsi+pei. 利用BitDecomp把c转化为一个l×l矩阵C，如下：(12)其中，是一个二进制多项式.然后计算C′=Flatten(Il·m+C)，其中，Il为l×l单位矩阵.C′即为消息m对应的密文矩阵.解密算法Dec：取矩阵C′的最后一行，并应用BitDecomp-1，如下：(13)m=⎣C0 f」=modp(14)密文计算算法Eval：(15)(16)5 方案分析5.1 正确性分析由加密算法可知：C=BitDecomp(cT)(17)其中，c(i,j)表示二进制多项式中第j项的系数. Il·m+CC′=Flatten(Il·m+C)(18)Flatten函数是把上面的矩阵转化为0/1矩阵. 取矩阵C′的最后一行，计算=BitDecomp-1(c(0,l-1),c(0,l-2),…,c(0,0)+m)(19)∴ C0=m+c0=m+hs0+pe0(20)C0 f=(m+hs0+pe0)f=mf+pgf-1s0 f+pe0 f =mf+pgs0+pe0f(21)⎣C0 f」modp =(mf+pgs0+pe0 f)modp =mfmodp(22)∵ f≡1(modp)∴ ⎣C0 f」modp=m(23)证毕.5.2 同态性分析加法同态：是把上面的矩阵转化为0/1矩阵.下面对按照同态解密算法进行解密.取上述矩阵的最后一行，并应用BitDecomp-1，如下：BitDecomp-1(c1(0,l-1)+c2(0,l-1),…,c1(0,0)+m1+c2(0,0)+m2)=m1+m2+c1(0)+c2(0)=C3其中，c1(0)=hs1(0)+pe1(0)，c2(0)=hs2(0)+pe2(0). ⎣C3f」modp=(m1+m2+hs1(0)+pe1(0)+hs2(0)+pe2(0))fmodp =(m1+m2+pgf-1s1(0)+pe1(0)+pgf-1s2(0)+pe2(0))fmodp=m1+m2加法同态得证.乘法同态：(24)把上述矩阵转化为0/1矩阵.下面对按照同态解密算法进行解密.上述乘法所得矩阵的最后一行的元素为：c1(0,l-1)·[c2(l-1,l-1)+m2]+c1(0,l-2)·c2(l-2,l-1)+ …+[c1(0,0)+m1]·c2(0,l-1)c1(0,l-1)·c2(l-1,l-2)+c1(0,l-2)·[c2(l-2,l-2)+m2]+ …+[c1(0,0)+m1]·c2(0,l-2)⋮c1(0,l-1)·c2(l-1,0)+c1(0,l-2)·c2(l-2,0)+…+[c1(0,0)+m1]·[c2(0,0)+m2](25)对最后一行的元素应用BitDecomp-1，结果如下：2l-1c1(0,l-1)·c2(l-1,l-1)+2l-1c1(0,l-2)·c2(l-2,l-1)+ …+2l-1c1(0,0)·c2(0,l-1)+2l-2c1(0,l-1)·c2(l-1,l-2) +2l-2c1(0,l-2)·c2(l-2,l-2)+…+2l-2c1(0,0)·c2(0,l-2) +…+c1(0,l-1)·c2(l-1,0)+c1(0,l-2)·c2(l-2,0) +…+c1(0,0)·c2(0,0)+2l-1c1(0,l-1)·m2+2l-1c2(0,l-1)·m1+2l-2c1(0,l-2)·m2+2l-2c2(0,l-2)·m1+…+c1(0,0)·m2+c2(0,0)·m1+m1·m2上式=c1(0,l-1)·c2(l-1)+c1(0,l-2)·c2(l-2)+…+c1(0,0)·c2(0)+c1(0)·m2+c2(0)·m1+m1·m2=C3上式中的c1(i)和c2(i)均为0的加密，其中i=0,…,l-1.即c1(i)=hs1(i)+pe1(i)，c2(i)=hs2(i)+pe2(i).⎣C3 f」modp=[c1(0,l-1)·c2(l-1)+c1(0,l-2)·c2(l-2)+…+c1(0,0)·c2(0)+c1(0)·m2+c2(0)·m1+m1·m2]fmodp(26)将c1(i)=hs1(i)+pe1(i)，c2(i)=hs2(i)+pe2(i)，h=pgf-1，f ≡ 1(modp)带入式(26)，得：⎣C3 f」modp=m1·m2(27)乘法同态性得证.5.3 安全性分析定理在RLWEd,q,χ的困难假设下，本文的全同态加密体制是IND-CPA安全的. 证明定理证明采用基于游戏的Game-Hopping方法，游戏中包含一个多项式时间的敌手A，用AdvIND-CPA(A)表示敌手A在游戏中获胜的概率.Game0：标准的IND-CPA游戏，即，挑战者调用全同态加密体制的KeyGen算法，将生成的公钥pk=h交给敌手A.A具备访问加密预言机的能力.挑战者输出挑战密文c=Encpk(mb)，敌手A尝试区分c所对应的明文mb，b∈{0,1}.Game0中敌手A的优势为(28)Game1：Game1与Game0的区别在于公钥pk的生成方式.Game1中的公钥pk 不通过私钥sk=f和高斯抽样算法得到，而是直接从中随机均匀选取.文献[20]中指出，根据离散高斯分布输出的样本与上的均匀分布是概率不可区分的.因此，敌手A无法区分Game0与Game1，有|AdvGame1(A)-AdvIND-CPA(A)|=0(29)Game2：Game2与Game1的区别在于Game2中的加密算法不再按照全同态加密体制中的改进后的NTRU加密算法进行加密，而是直接从{0，1}l×l中随机均匀选取.由文献[19]可知，BitDecomp，BitDecomp-1，Flatten操作并不会对方案的安全性产生影响.根据文献[23]中NTRU加密体制到RLWE问题的规约，可知Game2与Game1中，敌手A的优势差在于解决RLWE问题的优势|AdvGame2(A)-AdvGame1(A)|=RLWEd,q,χAdv(A)(30)Game3：在Game3中，挑战者给出的挑战密文c不再由加密算法生成，而是随机均匀地从{0，1}l×l中随机均匀选取.Game3的安全性分析与Game2相同，有|AdvGame3(A)-AdvGame2(A)|=RLWEd,q,χAdv(A)(31)至此，在Game3中，挑战者给出的公钥pk，挑战密文c都是随机的，与明文mb,b∈{0,1}没有关系.因此，敌手A在Game3中的优势为0，即AdvGame3(A)=0(32)综上，由式(28)～(32)可得AdvIND-CPA(A)=RLWEd,q,χAdv(A)+RLWEd,q,χAdv(A)因此，在RLWEd,q,χ的困难假设下，AdvIND-CPA(A)可忽略，本文的全同态加密体制是IND-CPA安全的.6 小结NTRU加密体制是后量子加密算法中最受青睐的算法，以其高速的加解密速度得到了十分广泛的应用，而且，目前并没有发现NTRU算法不能抵抗的量子攻击.但是，它的可证明安全问题一直是一个悬而未决的问题.全同态加密是目前密码学研究的热点问题，在云计算、密文检索、安全多方计算等方面都有广泛应用.本文基于原始的NTRU加密体制，提出一种新的NTRU加密体制.基于改进后的加密体制，利用Flattening技术，提出一种基于NTRU加密体制的全同态加密算法，在标准模型下证明了全同态加密方案选择明文攻击的不可区分性IND-CPA安全.参考文献【相关文献】[1]RIVEST R L,ADLEMAN L,DERTOUZOS M L.On data banks and privacy homomorphisms[A].Foundations of Secure Computation[C].USA:AcademiaPress,1978.169-179.[2]GAMAL T E.A public key cryptosystem and a signature scheme based on discrete logarithms[A].Proceedings of CRYPTO 84 on Advances in Cryptology[C].NewYork:Springer-Verlag,1985.10-18.[3]GOLDWASSER S,MICALI S.Probabilistic encryption & how to play mental poker keeping secret all partial information[A].Proceedings of Fourteenth ACM Symposium on Theory of Computing[C].New York:ACM,1982.365-377.[4]PAILLIER P.Public-key cryptosystems based on composite degree residuosityclasses[J].Lecture Notes in Computer Science,1999,547(1):223-238.[5]RIVEST R,SHAMIR A,ADLEMAN L M.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM,1978,26(2):96-99.[6]GENTRY C.A Fully Homomorphic Encryption Scheme[D].USA:Stanford University,2009.[7]DIJK M V,GENTRY C,HALEVI S,et al.Fully homomorphic encryption over theintegers[J].Lecture Notes in Computer Science,2009，(4):24-43.[8]BRAKERSKI Z,VAIKUNTANATHAN V.Efficient fully homomorphic encryption from (standard) LWE[A].Proceedings of Foundations of Computer Science[C].USA:IEEE,2010.97-106.[9]MANDAL A,TIBOUCHI M.Fully homomorphic encryption over the integers with shorter public keys[A].Proceedings of Conference on Advances in Cryptology[C].NewYork:Springer-Verlag,2011.487-504.[10]CORON J,NACCACHE D,TIBOUCHI M.Public key compression and modulus switching for fully homomorphic encryption over the integers[A].Proceedings of International Conference on Theory and Applications of Cryptographic Techniques[C].NewYork:Springer-Verlag,2012.446-464.[11]YAGISAWA M.Fully homomorphic encryption without bootstrapping[J].ACM Transactions on Computation Theory,2015,6(3):1-36.[12]HALEVI S,SHOUP V.HElib,Homomorphic EncryptionLibrary[OL].http://shaih.github.io/HElib/,2012.[13]李顺东,王道顺.基于同态加密的高效多方保密计算[J].电子学报,2013,41(4):798-803.LI Shun-dong,WANG Dao-shun.Efficient secure multiparty computation based on homomorphic encryption[J].Acta Electronica Sinica,2013,41(4):798-803.(in Chinese) [14]辛丹,顾纯祥,郑永辉,光焱,康元基.利用RLWE构造基于身份的全同态加密体制[J].电子学报,2016,44(12):442887-2893.XIN Dan,GU Chun-xiang,ZHENG Yong-hui,GUANG Yan,KANG Yuan-ji.Identity-based fully homomorphic encryption from ring learning with errors problem[J].Acta Electronica Sinica,2016,44(12):2887-2893.(in Chinese)[15]CHEN H,YUPU H,LIAN Z.Double batch for RLWE-based leveled fully homomorphic encryption[J].Chinese Journal of Electronics,2015,24(3):661-666.[16]HOFFSTEIN J,PIPHER J,SILVERMAN J H.NTRU:a ring-based public key cryptosystem[A].Proceedings of the 3rd International Symposium on Algorithmic Number Theory[C].Berlin:Springer,1998.267-288.[17]杨铭,曹云飞.NTRU的应用前景分析及展望[J].信息安全与通信保密,2007,(8):36-38.YANG Ming,CAO Yun-fei.Application prospect and analysis of NTRU[J].Information Security and Communications Privacy,2007,(8):36-38.(in Chinese)[18]TROMER E,VAIKUNTANATHAN V.On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[A].Proceedings of Forty-Fourth ACM Symposiumon Theory of Computing[C].New York,ACM,2012.1219-1234.[19]GENTRY C,SAHAI A,WATERS B.Homomorphic Encryption from Learning with Errors:Conceptually-Simpler,Asymptotically-Faster,Attribute-Based[M].Berlin:Springer,2013.75-92.[20]GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions[A].Proceedings of DBLP[C].Germany:DBLP,2008.197-206. [21]LYUBASHEVSHY V,PEIKERT C,REGEV O.On ideal lattice and learning with errors over rings[A].Proceedings of Eurocrypt 2010[C].New York:Springer-Verlag,2010.1-23. [22]张建航,贺健,胡予濮.基于R-LWE问题的新型NTRU加密方案[J].电子科技,2012,25(5):76-78. ZHANG Jian-hang,HE Jian,HU Yu-pu.A novel NTRU encryption scheme based on R-LWE problem[J].Electronic Science and Technology,2012,25(5):76-78.(in Chinese)[23]STEINFELD R.Making NTRU as secure as worst-case problems over ideallattices[A].Proceedings of International Conference on Theory and Applications of Cryptographic Techniques:Advances in Cryptology[C].New York:Springer-Verlag,2011.27-47.。

密码学报 I S S N 2095-7025 C N 10-1195/T NJournal of Cryptologic Research, 2020, 7(5): 683-697 ©《密码学报》编辑部版权所有.E-m a i l:j c r@c a c r n e t.o r g.c n h t t p://w w w.j c r.c a c r n e t.o r g.c nT e l/F a x:+86-10-82789618—个基于N T R U的多密钥同态加密方案#李瑞琪'贾春福W1.南开大学网络空间安全学院，天津3003502.天津市网络与数据安全技术重点实验室，天津300350通信作者：贾春福，E-m a i l:cfjia@n a n k a i.e d u.c n摘要：当前有关多密钥全同态加密的研究仍存在很多问題有待解决，如现有多密钥全同态加密方案的构造方法较为复杂；在云计算环境下，用户端的计算开销较大.针对上述问题，利用工具向量（g a d g e t v e c t o r)和比特分解（b i t d e c o m p o s i t i o n)技术，提出了一个基于N T R U的层级多密钥全同态加密方案，并给出了噪声增长与安全性的分析.该方案可以将之前方案中在同态运算阶段应用的重线性化（r e l i n e a r i z a t i o n)技木或密文扩张过程移除，进而在生成参数和密钥时元需生成运算密钥（e v a l u a t i o n k e y)或密文扩张所需的公共参数.同时，可以证明能够利用G e n t r y的b o o t s t r a p p i n g定理将该方案转化为完全的多密钥全同态加密方案.此外，该方案允许加密一个环中元素而不仅是1比特，从而可以利用中国剩余定理将该方案转化为支持批处理的多密钥同态加密方案.该方案与现有多密钥同态加密方案对比结果显示，该方案更加简洁，用户端的计算开铕相对较低.关键词：全同态加密；多密钥；N T R U;比特分解；批•处理中图分类号：T P309.7 文献标识码：A D O I: 10.13868/j.c n k i.j c r.000399中文引用格式：李瑞琪，贾春福.一个基于N T R U的多密钥同态加密方案问.密码学报.2020, 7(5): 683-697.[D O I: 10.13868/j.c n k i.j c r.000399]英文引用格式：L I R Q,J I A C F.A m u l t i-k e y h o m o m o r p h i c e n c r y p t i o n s c h e m e b a s e d o n N T R U[J j.J o u r n a l o f C r y p t o l o g i c R e s e a r c h, 2020, 7(5): 683-697. [D O I: 10.13868/j.c n k i.j c r.000399]A M u lti-k ey H om om orp h ic E n cryp tion S ch em eB ased on N T R UL I R u i-Q i1'2,J I A C h u n-F u1，21. College of C yb er Science, N ankai University, T ianjin 300350, C hina2. T ianjin Key L ab o rato ry of N etw ork an d D a ta Security Technology, T ian jin300350, C hinaC orresponding au th o r: JIA C hun-Fu, E-mail: cfjia@A b s t r a c t:T h e r e a r e m a n y p r o b l e m s t o b e s o l v e d o n t h e t o p i c o f m u l t i-k e y f u l l y h o m o m o r p h i c e n c r y p t i o n s c h e m e s.T h e e x i s t i n g M K F H E s c h e m e s a r e u s u a l l y c o m p l i c a t e d a n d dif f i c u l t t o i m p l e m e n t, w h i c h c a n c a u s e e x p e n s i v e c o m p u t a t i o n a l o v e r h e a d f o r u s e r s i n t h e c l o u d c o m p u t i n g e n v i r o n m e n t. T h i s p a p e r p r e s e n t s a l e v e l e d m u l t i-k e y f u l l y h o m o m o r p h i c e n c r y p t i o n s c h e m e b a s e d o n N T R U,a n d a n a l y z e s its n o i s e g r o w t h a n d s e c u r i t y.T h e g a d g e t v e c t o r a n d b i t d e c o m p o s i t i o n t e c h n i q u e s a r e u s e d +基金项目：国家重点研发计划（2018YFA0704703);国家自然科学基金（61972215, 61702399, 61972073);天津市自然科学基金（17JCZDJC30500)Foundation: National Key Research and Development Program of China (2018YFA0704703); National N atural Science Foundation of China (61972215, 61702399, 61972073); N atural Science Foundation of Tianjin M unicipality (17JCZDJC30500)收稿日期：2019-09-05 定稿日期：2019-12-02684Jem m a/ 〇//?esecirc/i 密码学报 Vol.7，No.5, O ct.2020i n t h e p r o p o s e d s c h e m e s u c h t h a t r e l i n e a r i z a t i o n o r c i p h e r t e x t e x t e n s i o n p r o c e d u r e c a n b e a v o i d e dd u r i n g t he h o m o m o r p h i c e v a l u a t i o n,a n d t h e r e is n o n e e d t o g e n e r a t e e v a l u a t i o n k e y o r p u b l i c c o m m o np a r a m e t e r s r e q u i r e d d u r i n g c i p h e r t e x t e x t e n s i o n.It c a n b e s h o w n t h a t,u s i n g G e n t r y’s b o o t s t r a p p i n g t h e o r e m,t h e p r o p o s e d s c h e m e c a n b e t r a n s f o r m e d i n t o a p u r e m u l t i-k e y f u l l y h o m o m o r p h i c e n c r y p t i o n s c h e m e.M o r e o v e r,t h e p r o p o s e d s c h e m e c a n e n c r y p t a r i n g e l e m e n t r a t h e r t h a n a s i n g l e b i t,s o it c a n b e c o n v e r t e d i n t o a b a t c h e d m u l t i-k e y h o m o m o r p h i c e n c r y p t i o n s c h e m e u s i n g C h i n e s e R e m a i n d e rT h e o r e m.T h e p r o p o s e d s c h e m e is c o m p a r e d w i t h e x i s t i n g o n e s,a n d t h e c o m p a r i s o n s h o w s t h a t t h e p r o p o s e d s c h e m e is m o r e c o n c i s e a n d u s e r s h a v e l o w e r c o m p u t a t i o n a l o v e r h e a d i n t h e c l o u d c o m p u t i n ge n v i r o n m e n t.K e y w o r d s:f u l l y h o m o m o r p h i c e n c r y p t i o n;m u l t i-k e y;N T R U;b i t d e c o m p o s i t i o n;b a t c hi引言全同态加密（F u l l y H o m o m o r p h i c E n c r y p t i o n,F H E)是-•种新型密码学工具，其支持在加密信息上 进行任意函数运算，并且解密后得到的结果与在明文上执行相应运算的结果一致.全同态加密的特性使其 能够广泛应用于云计算、物联网等多种计算场景.同态加密的思想最初由R i v e s t等人⑴在1978年提 出（最初的概念被称作“p r i v a c y h o m o m o r p h i s m”)，但在此之后一直都没有具体的构造方法，直到2009年 G e n t r y才构造出了第一个全同态加密方案I2'3!.在G e n t r y的开创性工作之后，一系列关于全同态加密的 研究成果相继出现+81.多密钥全同态加密（M u l t i-K e y F u l l y H o m o m o r p h i c E n c r y p t i o n,M K F H E)是 F H E 在多用户场景 下的一种推广，其支持多方用户以各自的密钥对消息进行加密，得到的密文可以一起参与运算，运算结束 后将各参与方的密钥收集起来得到联合密钥，再用联合密钥对结果密文进行解密.M K F H E在安全多方计 算中有着重要应用.当前有关N1K F H E方案构造的研宄主要可以分为以下三类：•基于N T R U方案.L6p e z等首次提出了 M K F H E的概念，并且构造了第一个M K F H E方案下称L T V12方案)，该方案是基于N T R U加密体制队叫的.作者利用重线性化（r e l i n e a r i z a t i o n)和模交换（m o d u l u s s w i t c h i n g)技术获得一个层级多密钥全同态加密（l e v e l e d M K F H E)方案.•基于 G e n t r y-S a h a i-W a t e r s (G S W)方案.2015 年，C l e a r 等丨叫构造了一个以 G S W 方案[7’12丨为基础的M K F H E方案，随后M u k h e r j e e等1131对C l e a r的方案进行了改进.由于这两个方案需 要在进行密文运算前就确定所有参与的用户，因此这两个方案被称作单跳的（s i n g l e-h o p).相对应 地，P e i k e r t等[141在2016年提出了多跳的（m u l t i-h o p)M K F H E方案（下称P S16方案)，其支持 运算得到的结果密文继续参与到接下来的计算中，也支持新用户中途加入运算.同年，B r a k e r s k i 等1151提出了与多跳类似的概念---全动态（f u l l y d y n a m i c),并构造了一个全动态的M K F H E方案（下称B P16方案)，该方案支持任意用户在任意时刻加入运算.多跳与全动态的区别仅在于是 否需要在同态计算前输入参与运算的用户数的上限..基于B r a k e r s k i-G e n t r y-V a i k u n t a n a t h a n (B G V)方案.2017 年，C h e n 等[16】提出了一个基于B G V问方案的M K F H E方案（下称C Z W17方案).该方案支持加密环中的元素而不只是1比特，并且该方案能够加入批处理机制.上述三种类型的方案推动了 M K F H E的研究，但仍然存在着一定的问题.这些方案存在的最主要问 题是，参与运算的用户除了生成公私钥以及对消息进行加解密外，还需产生大量额外的参数以保证多密 钥的同态密文计算能够进行，例如L T V12方案、B P16方案和C Z W17方案中需要用户生成运算密钥(e v a l u a t i o n k e y),P S16方案贝I]需要用户生成e x t e n s i o n k e y或冗余的密文，这增加了用户端的计算开销. 另外，基于B G V和基于G S W的方案都需要进行密文扩张，因为这两类方案中解密密钥的维数会随着用户数的增加而增加，这使得密文的尺寸也要随之增加才能正确解密.为了解决上述问题，我们提出了一种新的多密钥同态加密方案，利用工具向量和相应的分解函数将 N T R U方案转化成l e v e l e d M K F H E方案.本文所提方案的主要优势在于：李瑞琪等：一个基于n t r u的多密钥同态加密方案685•用户端只需要生成公钥和私钥以及对消息进行加解密，并不需要生成e v a l u a t i o n k e y或其他额外 的参数，减轻了用户端的计算负担.•使用比特分解技术来构造H E方案，这使得密文加法和乘法能够简单地实现，不需要加入其它辅助 技术（如r e l i n e a r i z a t i o n);也使得N T R U直接转化为l e v e l e d M K F H E方案，从而不需要m o d u l u s s w i t c h i n g技术.整个方案更加简洁、易于实现.•不需要进行密文扩张，即密文的（最大）尺寸是不变的.•支持加密环中的元素而并不只是1比特，因而本方案可以扩展成支持批处理的M K F H E方案.另夕卜，我们的方案是一个l e v e l e d M K F H E方案，仍需要利用G e n t r y的b o o t s t r a p p i n g定理将l e v e l e d M K F H E方案转化为一个完全的M K F H E方案.2预备知识本文中我们使用加粗大写字母表示矩阵，如M;使用加粗小写字母表示向量，如1；.在矩阵中，表示位于第i行第j列的元素；在向量中，表示向量中的第i个元素.矩阵和向量中的元素标号从1开始.本文中运算符“•”表示矩阵乘法，包括矩阵-矩阵乘法和标量矩阵乘法（向量可以看作n x 1或者 1x n的矩阵).令必m〇r)为分圆多项式，其次数为n =#(•；)为欧拉函数.本文涉及到的所有运算均在环7? =Z[a：V〈0m(x)〉中进行，令：=尺/研，&中元素的系数都在区间{-L g/2」，...，k/2」}内.定义环中元素 a=a…-i x n_1 +a…—2X n-2 +---h a#+a〇 的无穷范数为 ||a||〇〇 =m a x|a i|.下面的引理给出了环尺中多项式加法和乘法后范数的增长情况：引理1令只=Z[x^〈0m(x)〉，对于任意的a,6 G仏c G Z，有||a+b\\〇〇 < ||a||〇〇+ ||^>||〇〇||c-a||〇〇 < |c| • ||a||〇〇||a•b\\〇c<S■H a l l o o•||6||〇〇其中5是一个只与环丑有关的常数，称作环常数.2.1离散高斯分布我们将均值为0、标准差为r的离散高斯分布记作Z)Z n，r.在本文中唯一需要用到的有关离散高斯分 布的性质是，从中抽取的样本的范数大概率在某一范围内.由此我们可以定义如下的概念：定义1网如果一族分布丨X n^e N满足P r[||e||〇〇 >B] =n e g l(n)e—X n则称其为s界分布.而离散高斯分布有如下性质：引理2 W令n e N.对于满足r >u;(v/I^)的离散高斯分布〇Z n,T•，有P r[||x|U >< 2~"+1X i— D jr n r本文中所涉及到的离散高斯分布均定义为B界分布.由引理2可知，离散高斯分布£>z n,r■是一个 界分布.另外，结合定义1和引理1可以直接得到下面的推论.686Jo u m a/ 〇/C n/pbZ即zc 7?e<searc/i 密码学报 Vol.7,No.5, O c t.2020推论1间令i? =Z l#〈办m(a〇>.令X为丑上的S界分布，设/i,/2,...，A — X，有f c<s k~i B k2.2 R1A V E问题与D S P R•假设环上带错学习问题（R i n g L e a r n i n g W i t h E r r o r s,R L W E)最初是由L y u b a s h e v s k y等丨17丨提出的，判别版本的R L W E问题定义如下：定义2 1171设1/(入）为集合X上的均匀分布.给定一个秘密多项式s e—个上的分布X，我们定义一个A x上的分布九,x:随机选取a叫仏)，随机抽取…个差错e — X，输出(a，b=a.s+e).判别版本的RLW E问题（记作DRLWE^)定义为：当s — [/(&)时，区分儿,x与U(凡,x 7?9)两个分布.F面的定理阐述了问题D R I A V E+x的困难性，即区分4S,X与[/(/^ x这两个分布是困难的.定理1令么n(a〇为分圆多项式，其次数为n =V5(m).令a > 0, 9为素数且满足g = 1m o d m和a g 2w(v l^).那么，存在一个多项式时间的量子规约算法，将7? =Z丨〇:]/〈冷m〇r)〉中理想格上的近似 因子为 <5(^/^/〇)的近似最短线性无关向量问题（A p p r o x i m a t e S h o r t e s t I n d e p e n d e n t V e c t o r P r ob l e m,A p p r o x i m a t e-S I V P)规约到D R L W E q问题，其中分布x为满足r >的离散高斯分布D z'r.文献[18]中的引理2证明了秘密多项式s并不必须从上的均匀分布中随机选取，而是可以从选 取差错e的分布x中选取，因此在本方案中，为减缓噪声的增长速度，s和e均从分布x中选取.L c j p e z 等在文献间中介绍了D S P R(D e c i s i o n a l S m a l l P o l y n o m i a l R a t i o)问题，定义如下：定义3间令0(x)G Z[.r]是次数为r i的多项式，9为素数，x是环i? =Z M/W O e)〉上的一个分布.D S P R问题（记作D S P R^J定义为区分以下两个分布：•h=3/一1服从的分布，其中/,5是从分布X中随机选取的（这里要求/在中可逆)；•/?<(上的均匀分布.此前有关N T R U的研宄19’1Q，19 211己经证明，当</>(〇：)为任意分圆多项式，分布x为离散高斯分布 为分圆多项式的次数)，并且r > ^.P〇l y(n)时，D S P R a9,x问题是困难的（即定义3中的两个 分布在统计意义上是接近的).然而，为了能够进行多密钥同态密文计算，我们需要进行如下的假设：假设1令是次数为n的分圆多项式，分布x为离散高斯分布假设当r =p o l y(n)时,D S P R n x问题仍是困难的.2.3多密钥同态加密-个多密钥同态加密方案包含四个算法（K e y G e n，E n c，D e c,E v a l),具体描述如下：•(P k，s k)i K e y G e n(l A):给定安全参数A，输出公钥p k和私钥s k;•c— E n c(p k，m):输入消息明文m和公钥p k，输出密文c;•m:=D e c(s k i，s k2，...,s k；v，c):输入密文c，以及密文所对应的运算参与方的私钥s k b s l^.^s k i v，输出消息明文m;•(c*，S):= ，(c t，S t)):算法的输入包括一个电路C，以及f个元组(C i，S,)，i e {1，...，<}.每个元组中包括一个密文c,和其对应的用户（密钥）集合算法的输出为结果密文f和其对应的用户（密钥）集合S=U S,:(在用户（密钥）集合中可以找到任意参与运 算的用户的公私钥).2.4 B o o t s t r a p p i n gG e n t r y在文献[2,3]中提出了 “b o o t s t r a p p i n g”技术，该技术利用重加密的思想更新密文，从而控制 噪声膨胀以保证解密正确性，进而实现任意次的密文同态运算.G e n t r y的b o o t s t r a p p i n g定理也可以用于 多密钥的场景.具体来说，该技术要求H E方案能够对“增强解密电路（a u g m e n t e d d e c r y p t i o n c i r c u i t,)”进行处理，同时也需要该H E方案具存弱循环安全性（w e a k l y c i r c u l a r s e c u r e).有关b o o t s t r a p p i n g技术 的更多细节参见文献[2,3].李瑞琪等：一个基于N T R U的多密钥同态加密方案687定义4令£为一个多密钥同态加密方案.该方案的增强解密电路/C1，C2定义为/C l，C2(sk i,sk2,... ,skyv) = 5.Dec(ski,sk2,... ,sk^, c i)A.Dec(sk i,sk2,••• ,skyv,C2)定义5如果一个公钥加密方案在敌手获得其私钥的所有比特的密文时仍然是I N D-C P A安全的，则称该方案具有弱循环安全性.结合定义4和5,可以得到多密钥版本的b o o t s t r a p p i n g定理如下：定理2如果一个多密钥同态加密方案能够同态运行其增强解密电路，并且具有弱循环安全性，那么该 方案就能转化为一个完全的多密钥全同态加密方案.2.5工具向量和比特分解函数文献丨22]中提出了“工具向量（g a d g e t v e c t o r)”沒及其对应的比特分解函数它们最初是用来操作中的整数的.本文中，我们将这两个概念推广到多项式环中使用，并且基不局限为2.对于模数（7和基令々=「l o g^l.定义工具向量为分=(1,〇;,〇;2,…，o A—1相应的分解函数 g_1定义为：g ' :R q^R e J xl此函数的输入为凡中的一个多项式a,输出一个随机（歹l l)向量x1€ 乂〃1满足g .a:1' =a m o(i q.对于行向量v e9—Y r)表示将g-1作用于v的每一个分量从而得到一个矩阵V e2.6中国剩余定理与批处理中国剩余定理（C h i n e s e R e m a i n d e r T h e o r e m,C R T)是一个重要的工具，该定理内容如下：定理3 %设只是•个环，是尺中两两互素的理想，于是有R ^=j ik=<s>i=lRh其中 <8^=1 畀表示笛卡尔积，即区)〉=1 耷={(〇丨，a2，...，a fc)|c U= 1，...，*}.假设p A—个素数且满足（P，m) =\以及/ = 1 mod m，那么对于分圆多项式0m〇r)，有必m(a:)=r t=1 m odp，其中每个/iOr)的次数为d.根据中国剩余定理可知R p =Z p[x]/0,…(i) =Zp[x]/f\(x)®Z p[x]//2(x)®®Zp[x]/f k{x) ^ (F p d)f c每一个Z p M A A b)可以看作一个“明文槽”，利用该同构可以将A：个F p(i中的明文用/?p中的一个元素 来表示，并且有如下性质：设（a0，a i，…，a n W b o A,... e (F p d)f c是两组明文，它们对应的中的元素分别是a，b，于是计算a+b相当于计算（a〇+b〇，a i +b i，…，a j t-i +b n)，计算a6相当于计 算（a〇f e〇，a i6i，...，afc—i(u'—i).利用上述原理，文献[24]提出了支持 S I M D(S i n g l e I n s t r u c t i o n M u l t i p l e D a t a)操作的H E方案.在此基础上，文献丨25]利用/?p上的自同构映射a(;r)并结合B e n e§/\V a k s i n a n置換网络，可以使明文槽中的元素进行任意置换（p e r m u t a t i o n).具体来说，伽罗瓦群G a l(Q[;c]/<^m(:r))中的元素为 自同构映射14：^，丨6忑；1，该伽罗瓦群包含了一个子群£； = {：1：4；^>=0，1，...，£^—1}.文献[25]证明了商群//=G a l〇Q丨可以使明文槽中存储的消息进行轮换（r o t a t i o n).因此，以群//所包 含的自同构映射为基础再结合B e n e S/W a k s m a n置换网络，b]"以实现明文槽中兀素的任意置换.3基于N T R U的多密钥同态加密方案3.1 N T R U 方案我们首先介绍N T R U方案，这是构造我们的M K F H E 方案的基础.688JoumaZ 〇/CVypioZogic _R esearc/i 密码学报 Vol.7, No.5,O ct. 2020给定安全参数A,设存在多项式时间的算法输出以下参数：素数g =g(A),分圆多项式0m(a〇(次数为 n=n(A) =W m))，5(；\)界分布X.方案的明文空间为=H p,p为小整数（例如2或3)，方案所涉及 到的所有运算均在环〈也中进行.N T R U方案由以下三个算法组成：•N T R U.K e y G e n(l A):随机抽取多项式/'，g卜x,令/ := p/' + 1.如果/在&中不可逆，那么重新抽取输出公钥和私钥pk := h =p g f^1 6 R q,s k := / 6•N T R U.E n c(p k，/i):随机抽取多项式s，e i x.输出密文c=hs+pe+fi €R q.N T R_U.D e c(s k，c):计算//=/.c6 输出H=fi'm o d p当l l/c丨丨〇c <g/2时，解密的结果是正确的，这是由于此时/c m o d g=/c.3.2基于N T R U的多密钥同态加密方案这一小节介绍我们的基于N T R U的多密钥同态加密方案.给定安全参数A，设存在多项式时间的算法，输出素数9 =以A)，分圆多项式次数为n =W m) =rz(A)),S(A)界分布 x.设基为 ％ 心=「l o g^^l，工具向量为 g = (l，w,w2，...明文空 间为，令p为小整数且满足p S w <g,所有的运算均在中进行.我们的多密钥同态加密方案包括以下四个算法：•M K H E.K e y G e n(l A):调用 N T R U.K e y G e n(l A),输出公钥和私钥p k~h =p g f-1 €R q,s k:= f e R•M K H E.E n c(p k,"):随机抽取々组S i，ei — x用于计算N T R U.E n c(/i，0)来得到々个“0的密文”，然后将得到的•^个0的密文组成一个向量C〇e最后输出密文c-.= c〇 +ng £R l q xlq•M K H E.D e c^s k^s k^，…，s k j v,c):析取每个私钥s k,:得到s k i = /i，令联合私钥为s k := / = /i/2…//v.计算并输出明文H =N T R U.D e c(/,c[l])•M K H E.E v a W C J c u A M c i&V.d c^S t)):设密文C l对应的用户（密钥）集合为&，密文c2对应的用户（密钥）集合为密文加法为C a d d =M K H E.A d d(c i,C2) =c i +C2 €R\x l,>密文乘法为c m u it =M K H E.M u l t(c U i c2) =c i •g~\c2)e同时，也需要输出c a d d和c m u l t对应的用户（密钥）集合S=&U S 2.李瑞琪等：一个基于N T R U的多密钥同态加密方案689 4方案分析本节将对我们提出的M K F H E方案的有关性质进行分析.4.1同态性分析设C，C为两个密文，其对应的明文分别为叫/i，对应的公私钥分别为令c a d d =C+占，C m u丨t =c.下面我们将说明使用联合密钥/= / . /可以将c a d d解密得到Ai+将C mult解密得到"•/i.对于加法我们有C a d d =C-f-C使用/= / ./解密C a d d时，需计算/ •C a d d[l],可得/*C a d d[l] =//•C(〇)[l]+//•C(〇)[l]+//(/X-h p>)g[l]由加密过程可知和是0的密文，于是有/ •c⑶[1]m o d p= 0和/•m o d p= 0.另外己知/三1 m o d p,/三1 m o d= 1,因此可以推出/ •c ad d[l]m o d p=p,从而加法正确.对于乘法我们有C m u l t= ^ 'Q(c)=(C(〇)-y_1(c)=C(〇) -^_1(c)+/i-c=C(〇) •p_1(c)+m(C(〇) +A•^)=c(〇) •g~\c)-I-[I•C(〇)I I-fl-g使用/=/•/解密c m u l t时，需计算/.c m u l t[l]•设f1⑷得到的矩阵为C e'可得/ •C m u l t[l] =f f^ +//(M•C(〇)[l])+//(/X•同样，我们己知c(〇)【l]和5(〇)[l]是0的密文，因此/ .c(0)[l]m o d p=0, /.m o d p=0.再加上己知 / e 1m o d p,/e 1m o d p,= 1，故可以推出/ •c m l,it[l]m o d p=n -fi从而乘法正确.在文献间的最初构造中，密文c2 +£需要使用联合私钥/2 ./解密，而密文c+52需要使用联合 私钥/./2解密，也就是说联合私钥会随着运算电路的变化而变化.但我们希望联合私钥仅与参与用户有 关，而与运算电路无关.在文献[8]中，作者利用r e l i n e a d z a t i o n技术解决了这个问题.而在本文中，我们 的M K F H E方案不需要额外添加任何技术就可以使得联合私钥只与参与用户有关，不受运算电路的影响. 下面我们来说明这一点.事实上只需证明在本方案中，仅使用私钥/就能正确解密密文c,nult =c.即可.690Jem m a/ 〇/CVyptoZopz'c /?esearc/i 密码学报 Vol.7, No.5,O c t.2020与上文类似，我们可将c•g q(c)表示为C •分_1(C)=c(0) •分一 1(c)+/X •〇(〇)+"•"•分设c=g—y c)e只&以' 用/解密时有/. Cmult[l] =/E c[i，l]c(0)[i] + /(" • c(〇)[l]) + / . /i •"己知 / .c(〇)[l]m o d p= 0, / s 1m o d p，故可以推出/ ■c m u it[l]m o d p=n-fi以上的推导说明了无论有多少个用同一公钥加密的密文相乘，解密时只需使用原私钥，这就意味着本方案 中的联合私钥与运算电路无关.4.2安全性分析N T R U型密码方案的安全性是基于RLW E问题的.在本方案中，考虑由公钥和密文向量中的一个 元素组成的二元组（/i =P S/_1,cM=/is+pe +a//^.若h是从上的均匀分布中选取的，并且 S,e — X，那么此时可以看作是从分布儿,x中选取的，因此我们需要保证选取的S和/能够使 得/i z p p/-1的分布与上的均匀分布是统计意义上接近的.文献[9，10，19-21]己经证明当r >M.p o l y h)时，D S P R^.m问题是困难的（即定义3中的两个 分布在统计意义上是接近的).然而正如前文所述，在多密钥场景中无法将r设定为r >.P〇l y(n),因此我们需要D S P R假设（即假设1),将r设定为P〇l y(n：).尽管D S P R假设未被证明是困难的，但是当 <j=2—,e G (0, D时，到目前为止仍然没有高效的方法去解决D S P R假设1261.根据定理1,我们可以得到如下的关于本方案安全性的结论.定理4当为分圆多项式，次数为n;x为离散高斯分布■〇z»,r，其中r =p o l y(n);g = 2n，e 6 (0, |)时，在D R L W E^与D S P R_,X的假设下，本方案是I N D-C P A安全的.4.3噪声分析在这一小节中，我们将分析执行同态运算的过程中，密文噪声的增长情况.首先，对密文的噪声进行定 义：定义6设c为一个密文，/为其对应的私钥.密文c的噪声定义为n o i s e(c) = ||/■c[l]||〇〇对于所有N T R U类型的方案，解密正确需要满足条件||/ .c||〇〇 $g/2.因此在本方案中，正确解密需 要保证密文噪声满足n o i s e(c X g/2.下面的引理给出了执行一次同态运算后密文噪声的增长幅度.引理3令c，c'是两个密文，它们对应的明文分别是&//，对应的用户（密钥）集合分别为令c和d之间执行一次同态运算（加法或乘法）后得到的密文所对应的用户（密钥）集合为S=氏U S2,且 ■S中包含i V个用户（密钥).解密c a d d =c+c'和c m u l t =c.g-H c')可以分别得到//+//和"■//.如 果 n o i s e(c) £i?，n o i s e(c’）幺五，那么进行一次同态运算后，有 n o i s e(c a d d)，n o i s e(c m u it) <参数p，w，5,n，B的定义见3.2节.证明：已知每个用户最初的私钥/,的范数上界为p s+i./S根据推论1可知l l/s||〇c <李瑞琪等：一个基于N T R U 的多密钥同态加密方案6911)N < W p S 广.对于加法有=||/sius2(c[l] + 〇[1])||〇〇=ll/saNSiC/si • c[l]) + /s!\s2(/f» ' cflD H oo<<5||/slW I/Sl 'CW IIO O +列/S ||oc ||/S2< 2{2p 5B )NE其中灸\而表示集合的差，即S 2 -&.显然我们可以得到2(2p 5S )N J 5 <，因此加法情况结论成立.对于乘法，令得到的矩阵为C ' e 丑^〃9,我们有< ^q\\f s C '[l , l]C(〇)[l]||cx3 + ||m /s C (〇)[1]||o o + ||/s /i M l |c< ^<5-^ll/sc(〇)[l]ll 〇〇 + <5|ll/sC(〇)[l ]||〇〇 + <52(^)2||/s ||< (^^2 + |)5II^s 2\S i (/S i C(〇)[1])||o o + <52(|)2||/s ||〇〇< ^+ \){2p 5B)N E + 5(^f (2pSB)N <(^n +^-5+^)(2P 6B )N E< 2p 2b 〇nS (2pSB)NE< (2pumSB)2NE其中，已知c '[i ，fc ] e 扎，以及e 丑p ，从而有丨1匚'[1，句|丨〇〇 < w /2,以及h l l o c l l /Z I U s p /2. c(0)，c ，(〇)是与c ，c ，在同一层的（〇的）密文，故而它们的上界一致，即||/C (0)K f i j /c h K 五.当 g = 2n<，e G (0, 时，上式中倒数第三个不等号成立；w > 1时，w + 1 < 2i V ，7V + 2幺2A T ，最后一个不我们注意到噪声中有项，如果我们依照文献[9,10,19-21]设定r > ^.p o l y (n )，再根据引理2, 可以得到S > v ^.p o l y (n )，那么当i V > 1时噪声不可能小于g /2,因此我们需要D S P R 假设（即假设1)， 将 r 设置为 r = p o l y (n )，即 S = p o l y (n ).下面的引理表明了本方案是一个l e v e l e d MK F H E 方案，同时也说明了在进行多方同态运算前，需要 预先设定用户数和运算电路深度的上界.引理4令9 = 2"'££(0，§)，乂为5界分布且丑=口〇以(〇).当密钥（用户）数斤和方案允许运算 的电路的深度i 满足本方案是一个l e v e l e d M K F H E 方案.证明：引理3给出了一次同态运算后密文噪声的增长情况，于是我们可以从初始密文中的噪声五〇 < 4p 2<5S 2开始计算L 层（乘法）运算后密文噪声的大小.经过i 层运算后，密文噪声增长为n o i s e (c m u i t ) — \\fs ■ c m u it [l ]||c x j等号成立.N L < 0{n e / l o g n ){(2p 〇jn 6B )2N )LE 〇 < (2pu ;n 6B )2N L +2692JournaZ 〇/CVyptok^ic i?esearc/i 密码学报 Vol.7, No.5, O ct. 2020为了能够正确解密，我们需要保证g g/2.已知p = 0(l)，w = 0(1),B =p o l y(n)，并 且文献[3]指出大多数情况下环常数<5满足<5=P〇l y(n)(这就要求我们选取满足此项要求的分圆多项式).根据上述条件可得N L < 0(l o g q/l o g n) =0(n£/l o g n)□4.4完全的多密钥全同态加密上文中我们得到的方案是一个l e v e l e d M K F H E方案.在这一小节中我们将说明，可以利用G e n t r y 所提出的b o o t s t r a p p i n g定理，将丨e v e l e d M K F H E方案转化为完全的M K F H E方案.G e n t r y在其开创性的工作％31中提出了 b o o t s t r a p p i n g定理，该定理指出如果一个同态加密方案能 够同态运行自己的增强解密电路，那么该方案就能够转化为一个完全的全同态加密方案.因此，需要对本 方案的解密电路的深度进行衡量.下面的引理给出了本方案解密电路深度的上界.弓丨理5本方案的解密电路可以用G F(2)上的深度为C»(l〇g i V.(l o g l〇g g+l〇g r a))的算术电路来实现.证明：假设c是密文，其对应的私钥集合为{/^方,...，/；v}，那么解密c的过程可以表示为NM K H E.DecC/i,/2,•■•,f N,c[l]) =c[l] ■/,i=l文献[4]己经证明，两个仏中的多项式的乘法可以通过深度为〇(l〇g l〇g g+l〇gn)的布尔电路来实 现.7V个多项式相乘可以通过深度为l o g7V的二叉树来实现，因此解密过程的布尔电路的深度为0(l o g7V• (l o g l o g^ +l〇g n))□根据上文的结论，我们得到定理5.定理5当g = 2n'e G(0，|)，x为召界分布且召=P〇M n)时，存在一个支持iV$1/^7^. (ne/2/l〇g n)个用户（C为常数)，安全性基于DRLWEg,x与DSPR^,X假设，且满足弱循环安全性的多 密钥全同态加密方案.证明：根据G e n t r y的b o o t s t r a p p i n g定理，要达到完全的全同态加密，解密电路的深度需要小于方 案能够同态运行的电路的深度，即对于某个常数C〉0,有如下不等式l o g A^•(l o g l o g^ +l o g n) <C•1〇S qN• log n当 .h e/2/1〇g几）时，有l o g N•(l o g l o g q+l o g n) ■N•l o g n <N2 •l o g n•(l o g l o g q+l o g n).C n e_ . . 2<2* ' 1^2^ '+€)'loS n<C-n€=C•l o g q从而得到定理中的结论.□4.5批处理利用中国剩余定理和文献I24j中提出的S I M D技术，可以将本方案转化为一个支持批处理的多密钥 同态加密方案.当选取合适的参数p和分圆多项式时，我们可以通过C R T将一组明文，//；〇映射为一个多项式，抖)，然后将"加密得到密文c.根据同态加密和C R T映射的特 性，并行加法和乘法可以分别通过密文加法和乘法实现.因此在本小节中，我们将主要讨论如何进行置换 运算.文献I25j提出了以自同构映射为基础来实现置换的方法，其中自同构映射是核心技术，下文将介绍 自同构映射在本方案中的应用.设密文C对应的明文为/i,对应的密钥为/ =/i/j…知，因此我们可知f(x)c(x) = n(x)g + pe(x)+(/>m(x)k(x)其中以办知⑷^/^^将自同构^:^:^:^泛^作用于该等式可得f(x l)c(xl)=n{xz)g+pe(xl)+(p m(xl)k(xl)己知0m〇r)能够整除彡€Z L从而我们可以将看作关于密钥/(V)的密文•然而 我们需要的密文应当是对应于密钥/(a〇的密文，因此我们在进行置换运算时，需要借助于密钥交换技术 (k e y s w i t c h i n g),将密文c〇c2)转化为一个新的密文c' =K e y S w i t c h W：^)),使得新密文能够用/⑷解密.下面将说明本方案中为实现置换运算所需要的密钥交换过程.设密文c(a;)对应的联合密钥为/⑷=/i(a;)/2(a〇•••/"(〇;)，密钥交换过程K e y S w i t c h k h1》分为 以下2步：•拥有密钥力的用户首先计算=M K H E.E n c^k，/^;^))，然后每个用户将各自的计算结果c t 发送到云端.•云端计算c，=c/i '9~\c h) ■■g~1{c f N)-g'^c^1))得到的计算结果c'即是所需的密文.下面说明K e y S w i t c h k W))输出的密文能够用联合密钥/解密.由加密过程可知，可以表示为 c/j =c(〇),A +其中是对应于/)的0的密文.于是有c/i'9_1(c/2) =c(0)i/l^~\〇/2) + f2{x')c{0)j2 + f i(x l)f2(xl)g在这个等式中，可以看作是对应于密钥A的0的密文，/2(;^)£：(0),/2可以看作是对应于 密钥/2的〇的密文，因此前两项之和.9_1(<；/2)+/2〇^)<=(0),/2可以看作对应于密钥/l/2的0的密文，我们将其记作c(0),/l/2，于是C/l的结果可以写作C/i' 9_1(c/2) =C(〇),/l/2+f i(x l)f2(x')g以此类推，我们能够得出c'可以表示为c，=c(〇),h h-f N+/i(x l)M x t)' ■'/n(x')c(x')=C(〇)i/l/2'-/jV f(X )C(X )其中C W A/l./i v是对应于密钥/ = /1/2...力V的0的密文.显然，当密文噪声不超过上界时，c'能够用 f =h f2. —f N 解密.5方案对比本节中我们将对比本方案与其他经典方案在性能上的差异.首先简要对比本方案与D o r f i z等人在2016年提出的方案（下称D S16方案）之间的异同.本方 案与D S16方案使用了类似的技术（即比特分解）来处理噪声的增长，但是不同之处在于D S16方案使用 了B i t D e c o m p、F l a t t e n等函数进行比特分解；本方案则利用工具向量g及其相对应的分解函数进行分解，此项差异造成了两个方案的密文大小以及同态运算的复杂度有所不同.设表示分圆多项式的 次数，g表示模数，那么D S16方案中密文的尺寸为0(n l o g3 g)，本方案中密文的尺寸为0(n l o g2g).相较 于D S16方案，本方案中的密文尺寸相对较小.在同态运算过程中，D S16方案需进行（维数为l o g q的，元 素为多项式的）矩阵加法和矩阵乘法，本方案则进行的是（维数为l o g g的，元素为多项式的）向量加法和 矩阵-向量乘法.相比之下，本方案的计算复杂度较低.另外，D S16方案讨论的是单密钥场景下的同态加 密算法，不需要D S P R假设；而本方案是多密钥场景下的基于N T R U的冋态加密方案，无法避免D S P R 假设.下面我们将与经典的多密钥同态加密方案进行对比.5.1与LTV12方案的比较本方案与L T V12方案都是基于N T R U的M K F H E方案，既有共同点也有不同点.两个方案在噪 声增长、可同态运行的电路深度等方面有着类似的结论，但是二者是利用不同的技术达成的.L T V12方 案利用r e lin e a r iz a tio n技术消除了联合私钥中的平方项，同时也实现了 key s w itc h in g的功能；又使用 了m o d u lu s s w itc h in g技术，将N T R U方案转化为一个leveled M K F H E方案.这两项技术的使用使 得L T V12方案必须在生成公私钥的同时生成运算密钥，并且在进行每一次同态运算（加法或乘法）时都 需要执行re lin e a riz a tio n操作，每一层同态运算后都要进行m odulus s w itc h in g,才能使得方案成为一个 leveled M K F H E方案.而本方案使用了工具向量和比特分解技术，使得实现同态运算所需的操作变得非 常简单，不需要额外的技术，并且直接将N T R U方案转化为一个leveled M K F H E方案.另外，实现本方案 的同态运算过程仅需要普通的多项式加法和乘法，以及一个将多项式分解的函数.相较于LTV12 方案，本方案更易于理解和代码实现.表1中列出了本方案与L T V12方案的一些基本参数之间的对比，其中n表示分圆多项式的次数，9 表示模数.从表1中可以看到，我们的方案不需要运算密钥，而L T V12方案需要尺寸为0(n l o g3g)的运 算密钥.虽然本方案在同态运算过程中的密文的尺寸是大于L T V12方案的（表1中密文尺寸一行)，但是 运算后得到的最终密文（解密时所需的密文）的尺寸与L T V12方案相同（表1中最终密文尺寸一行).表1与L T V12方案的基本性质的比较Table 1 Comparisons of basic properties with LTV12 scheme基本参数本方案L T V12方案公钥尺寸0{n\o g q)0(n log g)密文尺寸0(n log2 q)0(n log g)最终密文尺寸0(n log q)0(n log g)运算密钥/0(n log3 q)下面我们将对比本方案与L T V12方案在云计算场景下，用户端和云端分别所需执行的操作.将同 态加密算法应用于云计算场景时，用户端需要执行的主要操作是生成密钥和同态计算所需的参数（即运 行K e y G e n算法)，加密（E n c)和解密（D e c);云端进行的操作则是对用户上传的密文进行同态运算.我们 对两个方案在用户端所需的操作进行比较，因为在云计算场景中，我们希望用户端的开销能够尽可能地降 低.比较结果如表2所示.我们将表2中所列出的密钥生成和加密两个过程中用户端所做的操作综合起来进行对比：若加密1比特，本方案中用户端所需的全部操作是随机生成2个多项式，进行l o g g次多项式乘法和21〇g g次多项式 加法；L T V12方案中用户端所需的全部操作是随机生成2(l o g2 g+l o g(?)个多项式，进行6 l o g2<7+1次多。

ntru密码算法【原创实用版】目录1.NTRU 密码算法概述2.NTRU 密码算法的原理3.NTRU 密码算法的优缺点4.NTRU 密码算法的应用5.总结正文1.NTRU 密码算法概述TRU 密码算法是一种公钥加密算法，由美国密码学家 Bruce Schneier 和 Johannes Warns 在 1996 年提出。

NTRU 的全称是“Nested Triples”，即嵌套三元组，这种密码算法基于数学上的环和多项式理论，具有较高的安全性和效率。

2.NTRU 密码算法的原理TRU 密码算法的核心思想是将明文或密文转换为环上的多项式，通过数学运算实现加密和解密。

具体来说，NTRU 算法使用了三种基本数学结构：有限域、多项式环和椭圆曲线。

其中，有限域用于生成公钥和私钥，多项式环用于实现加密和解密，椭圆曲线则用于验证签名。

TRU 密码算法的具体步骤如下：（1）生成密钥：在有限域上选择一个元素作为私钥，计算其乘积得到公钥。

（2）加密：将明文转换为多项式，然后通过与公钥进行数学运算得到密文。

（3）解密：使用私钥对密文进行数学运算，得到明文。

（4）签名和验证：利用椭圆曲线实现数字签名，通过验证签名来确保数据的完整性和真实性。

3.NTRU 密码算法的优缺点优点：（1）安全性高：基于数学难题，NTRU 密码算法具有较高的安全性。

（2）性能优越：NTRU 算法的加密和解密速度较快，适用于各种网络通信场景。

（3）兼容性好：可以与 RSA、DSA 等其他密码算法共同使用，实现混合加密。

缺点：（1）密钥管理复杂：NTRU 算法需要处理大尺寸的密钥，可能导致密钥管理困难。

（2）算法成熟度较低：相较于 RSA、AES 等成熟密码算法，NTRU 算法应用较少，尚处于研究和发展阶段。

4.NTRU 密码算法的应用尽管 NTRU 密码算法目前应用较少，但其在网络安全领域具有潜在的应用价值。

例如，在物联网、云计算、移动支付等场景中，NTRU 密码算法可为数据传输提供高效、安全的加密保护。

无需重线性化的NTRU型全同态加密方案汤殿华;曹云飞【摘要】全同态加密由于具有密态计算功能,能够保证数据计算处理的信息安全,特别满足当前云计算,大数据的安全需求,这使得全同态加密具有广阔的应用前景,目前有许多全同态加密方案被提出,效率不断被改进,但全同态加密的效率仍然不够实用.聚焦于全同态加密的效率问题,提出了一个新的NTRU型全同态加密方案,与同类NTRU型方案相比,该方案去除了重线性化算法和同态计算密钥,并且具有更为简洁的同态操作,更小的噪声增长率,最后,我们给出两种方法使得方案达到自举性,从而转化为全同态加密方案.【期刊名称】《通信技术》【年(卷),期】2019(052)008【总页数】9页(P1948-1956)【关键词】重线性化;NTRU加密;全同态加密【作者】汤殿华;曹云飞【作者单位】保密通信重点实验室,四川成都610041;中国电子科技集团公司第三十研究所,四川成都610041;保密通信重点实验室,四川成都610041;中国电子科技集团公司第三十研究所,四川成都610041【正文语种】中文【中图分类】TN918.40 引言全同态加密是一种功能强大的加密技术，能够在加密数据上执行任意的计算，同时将对应的计算映射到相应的明文中，其计算结果是为密文。

可以说，全同态加密技术能够全密态处理数据。

采用该加密技术，用户可以将数据以加密形式外包给任何不可信服务器进行“密文计算”来获取服务，保证数据安全。

全同态加密技术具有广阔的应用前景，例如云安全、加密数据库、大数据安全、搜索引擎的加密询问等。

同态密码技术对我们并不陌生，例如RSA[1]、ElGamal[2]、Paillier[3]等加密方案。

这些加密算法都具有同态性，但只有单个同态运算性质，不能同时具有“加同态”和“乘同态”，以致不能够执行任意的密文计算。

1978年，Rivest，Adleman，Dertouzos[4]首次提出了“隐私同态”的概念，希望解决密文任意计算问题。