当今世界，大数据、云计算等蓬勃发展，使互联网时代迈上一个新台阶.然而，云计算和大数据所具有的数据集中、资源共享、高度互联、全面开放等特点，一方面打破了传统IT领域的信息孤岛，另一方面也带来了更严峻的安全问题.云计算模式的核心是数据，本质是服务，特点是“零信任”，因此，“数据在不可信环境下的安全计算(服务)”成为解决云计算安全的一个关键问题.2009年IBM实验室的Gentry首次给出了“全同态加密”(fully homomor-phic encryption, FHE)方案[1-2].全同态加密可以在不解密的情况下对密态数据进行各种运算，其结果在解密后与对明文进行相应运算的结果是一样的.全同态加密不仅能够对密文进行任意的盲操作，而且还能够对计算
操作行为本身进行加密的密码算法，因此，全同态加密真正从根本上解决了将数据及操作委托给第三方时的保密问题，使人们既可以充分利用云计算强大的计算和存储能力为用户提供海量密文处理服务，又可以自己管理保证数据安全的密钥，实现了“数据在不可信环境下安全计算(服务)”.
Gentry给出的FHE框架中利用bootstrapping技术实现了“全同态”特性，bootstrapping技术的关键环节是在服务器端对同态计算的密文实施周期性的重加密操作，即对密文进行刷新，从而实现降低噪声的目的.为此需要对私钥s的每一位进行加密，所得结果作为重加密的公钥.为了周期性实施重加密操作，需要引入公私钥链，公钥链(pk1,pk2,…,pkl+1)以及加密后的私钥链
其中
密钥链的长度l随着运算电路的深度线性增长.对于加密方案而言，只有加密方案满足密钥独立消息(key dependent message, KDM)安全，才可以保证加密方案在加密私钥相关消息的情况下也是安全的.因此，设计满足KDM的同态加密方案可以使得密钥链的长度与运算电路的深度无关，从而有效实现FHE方案公钥与密文规模约减，提高FHE方案的运算效率.
本文的主要贡献包括2个方面:
1) 给出了满足循环安全性的公钥同态加密方案，并给出了安全性证明和参数设置分析；
2) 通过引入拒绝采样技术，对上述满足循环安全性的同态加密方案进行了优化，将方案参数从超多项式级降低到多项式级，大大约减了参数规模，有效提升了方案的效率.
1 相关工作
关于循环安全的加密方案已有一些研究成果.Boneh等人基于无随机Oracle的DDH假设构造了一个循环安全的公钥加密方案[3].Applebaum等人根据基于错误学习(learning with error, LWE)问题的Regev加密方案[4]，构造了循环安全的有效密码体制[5].在循环安全的同态加密方面，杨晓元等人[6]基于LWE问题的变形给出了一个对私钥的线性函数满足循环安全的FHE方案，但是这个困难假设并不是一个标准的困难假设.Zhao等人[7]给出了矩阵GSW方案[8]满足循环安全性的一个充分条件，但是缺乏必要性证明.2011年美国密码学年会，Brakerski和Vaikuntanathan[9]基于环LWE问题给出了一个循环安全的同态加密方案，称为BV方案.BV方案实现循环安全性的基本思路是利用“噪声淹没技术”(noise flooding technique)，即在原加密方案的基础上，再引入一个“宽高斯”分布的噪声，从而使得对密钥加密的密文与对普通明文加密的密文不可区分.由高斯分布的叠加性和不可区分性，保证挑战者模拟私钥的密文.
本文给出的循环安全的公钥同态加密方案，通过引入拒绝采样技术有效约减了密文模的规模，提升了同态运算的效率.该研究成果可以为同态加密方案设计与实现提供理论参考.
2 基础知识
本节主要介绍本文用到的基本定义和重要的引理.
2.1 离散高斯分布
标准方差为σ、中心为c的高斯分布定义为
R.
对于∀x,c∈Rn,离散高斯的分布概率密文函数定义为
Z和Zn上的离散高斯分别定义为
引理1[10]. 令n∈N,对于任意的实数
有
引理2[11]. 令n∈N,对于任意的实数对任意的c∈Zn,DZn,σ和DZn,σ,c之间的统计距离至多为
引理3[12]. 令n∈N,m=2n,f(x)=xn+1,令R=Z[x](f(x)).对于任意的s,t∈R,
引理4[13]. 对于
有:
特别地，当n=1,r=6时，有:
引理5[14]. 令λ为安全参数.Φm(x)=xn+1是度为n=φ(m)=m2的m次分圆多项式.令σ≥
为一个实数，q≡1(mod m)为素数.令R=Z[x]
Φm(x)
,则存在一个从2ω(log n)×(qσ)-近似R-SVP问题到RLWEΦm,q,χ的随机归约算法，其中，χ=DZn,σ为离散高斯分布.归约算法的运行时间为poly(n,q).
2.2 拒绝采样
拒绝采样技术由Neumann提出，给出了通过源概率分布采样得到目标概率分布采样的一个方法[15].PKC2008，Lyubashevsky利用拒绝采样构造了基于格的身份识别协议[16].Crypt2013，Ducas等人利用拒绝采样构造了基于格的BLISS数字签名算法[17].NIST征集的多数后量子数字签名候选算法也采用了拒绝采样技术.
引理6. 拒绝采样.令V是任意一个集合，h:V→R和f:Zm→R为概率分布.若gv是以v为索引的一簇概率分布，并且存在一个M∈R，使得:
∀v∈V,∀z∈Zm,M.gv(z)≥f(z),
那么，2个算法输出的分布是相同的：
1) v←h,z←gv,以概率f(z)(M.gv(z))输出(z,v)；
2) v←h,z←f,以概率1M输出(z,v).
2.3 同态加密的循环安全性定义
如果密钥由相应的公钥加密后依然是安全的，那么加密方案才能实现循环安全，即循环安全加密方案可以抵抗密钥相关消息攻击.给定安全参数λ，令
为密钥空间，令f为从到
的函数.一个同态加密方案HE={KeyGen,Enc,Dec,Eval}关于f满足循环安全性，如果对于所有的PPT敌手
敌手
赢得下面游戏的概率是可忽略的：
1) 挑战者计算(pk,sk,evk)←KeyGen(λ),并随机选择一位b←{0,1}；
2) 令
为一个函数，计算f+(x,
挑战者计算挑战密文并发送给敌手
3) 敌手输出一个猜测位b′∈{0,1}.
敌手的优势定义为
在基于LWE的FHE方案中，Evalevk(f+,Encpk(0),f(sk))可以视为加密f(sk)的密文.
3 循环安全的公钥同态加密方案
文献[9]给出了对称版本的支持私钥sk的d次多项式的KDM安全同态加密方案，我们称为KDM.SKHE.这里，我们给出KDM安全的非对称版本的同态加密方案.令
为Rt上度为d的多项式集合，即:
为了实现对私钥sk的多项式p(sk)的KDM安全性，我们利用对称版本的方法，将标准的同态加密的密文(c0,c1)扩展为(c0,c1,…,cd)，其中d为多项式p(sk)的度.我们令d=2,即我们考虑对私钥sk的平方函数满足循环安全性的同态加密方案，记作KDM.PKHE.
3.1 方案描述
具体算法描述为：
1) KDM.PKHE.PamameterSet.令λ为安全参数.选择素数q,t∈Z
Z[x],以及多项式环Rq=Zqf(x)上的离散高斯分布DZn,σ和DZn,σ′.Rt为方案的明文空间.
2) KDM.PKHE.Keygen(1λ).随机选择a0∈Rq，从离散高斯分布采样得到s,e0←DZn,σ，计算b0=a0s+te0，输出私钥sk=s和公钥pk=(a0,b0).
3) KDM.PKHE.Enc(pk,m).对于消息m∈Rt,按照方式生成密文
首先生成2个二元组
其中
然后计算密文c0=b1+m;c1=b2-a1;c2=-a2.
4) KDM.PKHE.Dec(sk,c).令s=(1,s1,…,sd),计算
当
时解密正确，输出m=c,s mod t.
故上述无穷范数小于q2时,则可以解密成功.
3.2 循环安全性证明
为了给出KDM.PKHE方案的循环安全性证明，我们首先证明引理：
引理7. 设ξ和η是Zq上2个独立的随机变量，且ξ在Zq上服从均匀分布，那么ξ+η在Zq上也服从均匀分布.
证明. 设ξ和η独立，则∀z∈Zq,有:
Pr[ξ+η=z mod q]=
由ξ在Zq上服从均匀分布知:
因此有:
即ξ+η在Zq上服从均匀分布.
证毕.
推论1. 设ξ和η是Z
上2个独立的随机变量，且ξ在Z上服从均匀分布，η服从离散高斯分布DZn,σ，若
则:
{ξ+η}≈U(Z
即ξ+η的分布与Z
上的均匀分布计算不可不可区分.
证明. 已知η服从离散高斯分布DZn,σ，根据引理4，η分量ηi的取值大约以概率1-exp(Ω(τ2))满足|ηi|≤τσ.因此，若则η分量ηi的取值以概率1-exp(Ω(τ2))落于Zq内.利用引理7，可得ξ+η的分布与Z上均匀分布计算不可区分.
证毕.
定理1. 假设且σ′=2ω(log n)σ2，那么基于判定性RLWE假设，我们给出的公钥同态加密方案KDM.PKHE关于f(sk)=s2满足KDM安全性.
证明. 对于任意多项式时间的攻击者令赢得方案KDM安全实验的优势为ε.我们将通过实验G0,G1,G2来证明ε是可忽略的，从而完成定理1的证明.
实验G0. 实验G0是真实的KDM-CPA安全实验，如2.3节定义中所述.在该实验中，挑战者按照加密算法生成挑战密文
实验G1. 除了挑战密文的生成方式不同之外，实验G1和G0相同.实验G1中，挑战者按照2种方式生成f(sk)的挑战密文：
当b=0时，设置挑战密文为
当b=1时，设置挑战密文为
(c0=b1+0,c1=b2-a1,c2=-a2).
其中，
证毕.
引理8. 假设离散高斯参数满足σ′=2ω(log n)σ2和
则敌手区分实验G1和G0的概率是忽略的,即:
(1)
证明. 对于消息s2∈Rt，考察同态加密方案的密文c0：
(2)
令
则式(2)等于
已知
的分布服从DZn,σ′,令e0v1-e1s=E，根据引理1和引理2有：
令Δ=2n1.5σ2，由σ′=2ω(log n)σ2，有:
根据引理2，离散高斯分布DZn,σ′和离散高斯分布DZn,σ′,Δ的统计距离是可忽略的,从而有
e0v1-e1s的分布与的分布不可区分.因此，挑战者模拟的挑战密文
与真实的密文c0是不可区分的.
另外，考察同态加密方案的密文c1：
(3)
令
则式(3)等于
同理由σ′=2ω(log n)σ2，可得噪声足以“淹没”e0v1-e1s，即
的分布与的分布不可区分.又
也服从Rq上的均匀分布.因此，敌手模拟的挑战密文
与真实的密文c1不可区分.
因此，敌手区分实验G1和G0的概率是忽略的，引理8成立.
实验G2：除了挑战密文的生成方式不同之外，实验G2和G2相同.实验G2中，挑战者按照2种方式生成f(sk)的挑战密文：
当b=0时，设置挑战密文为
当b=1时，设置挑战密文为
(c0=b1+0,c1=b2-a1,c2=-a2).
其中，ui(i=0,1,2)为环Rq中的随机元素.
证毕.
引理9. 假设离散高斯参数满足σ′=2ω(log n)σ2和则敌手区分实验G1和G0的概率是忽略的，即
(4)
证明.
是独立的，根据推论1，当
时,
的分布与Rq上的均匀分布不可区分，也即
和a1的均服从Rq上的均匀分布.由也服从Rq上的均匀分布.因此，
和
是RLWE问题的实例，从而有:
综上，有：
由于在实验G2中，挑战密文是与私钥s独立的均匀随机的环元素，因此敌手的优势是可忽略的，即：
(5)
综合式(1)(4)(5)，有:
至此，我们证明了敌手的KDM安全性实验中的优势是可忽略的.
证毕.
3.3 参数设置
KDM.PKHE方案中的参数并不是独立选择的，相互之间存在一些制约关系,下面给出详细分析.
1) 为了使得离散高斯分布DZn,σ′可以“淹没”DZn,σ上采样的2次多项式，要求σ′=2ω(log n)σ2.
2) 为了保证离散高斯分布DZn,σ的采样s位于明文空间Rt内，要求
3) 为了保证解密正确性，需要满足
即:
t×2ω(log n)×σ2<q2.
故密文模q满足q>t×2ω(log n)×σ2可保证解密正确性.
4 改进方案
为了利用噪声淹没技术实现循环安全性，离散高斯分布DZn,σ′的标准方差σ′需要满足σ′=2ω(log n)σ2，而解密正确性要求模数q>t×2ω(log n)×σ2，因此，模数q是n的超多项式函数，使得KDM.PKHE方案的效率极低.下面，我们以d=2这种情况为例，通过引入拒绝采样技术来约减σ′的规模，进而降低q的规模，并最终提高循环安全的KDM.PKHE方案效率.
4.1 方案描述
除了加密算法中噪声采样算法不同之外，改进方案同KDM.PKHE方案基本相同，记为RS.KDM.PKHE.
1) RS.KDM.PKHE.PamameterSet.令λ为安全参数.选择素数q,t∈ZZ[x],以及多项式环Rq=Zqf(x)上的离散高斯分布DZn,σ和DZn,σ′.Rt为方案的明文空间，Δ=2n1.5σ2.
2) RS.KDM.PKHE.Keygen(1λ).随机选择a0∈Rq，从离散高斯分布采样得到s,e0←DZn,σ，计算b0=a0s+te0，输出私钥sk=s和钥pk=(a0,b0).
3) RS.KDM.PKHE.Enc(pk,m).对于消息m∈Rt,按照如下方式生成密文
① 计算ai=a0vi+tei，其中vi,ei←DZn,σ.
② 重复采样
并以概率
计算
值得注意的是此处使用了拒绝采样技术，以一定概率对采样进行拒绝，其目的是通过拒绝采样降低参数σ′的规模.
③ 计算对m加密后的密文：
c0=b1+m;
c1=b2-a1;
c2=-a2.
4) RS.KDM.PKHE.Dec(sk,c).令s=(1,s1,s2),计算
当
时解密正确，输出m=c,s mod t.
4.2 方案正确性分析
在RS.KDM.PKHE方案的加密算法中，如果利用拒绝采样技术得到
与
的分布不可区分，即对DZn,σ上采样进行“淹没”，则可以实现循环安全性证明中密钥的密文是均匀随机分布，安全性证明过程与定理1证明类似.
下面我们分析如何选择σ′以及拒绝采样的重复次数M使得加密算法中采样的分布服从分布DZn,σ′.令e0vi-eis=Ei，根据引理1和引理2有:
如图1所示(n=1的情形)，我们令拒绝采样的目标概率分布是DZn,σ′，源概率分布是DZn,σ′,Ei.为了利用拒绝采样技术，我们需要找到实数M，使得对于所有的x∈Zn,有DZn,σ′(x)≤M×DZn,σ′,Ei(x).根据高斯分布的定义有：
其中，根据引理5，x,Ei至少以概率1-exp(-Ω(τ2))满足
令σ′=τΔ，则有：
Fig. 1 Reject sampling technique
图1 拒绝采样技术
因此，我们令
则根据拒绝采样的定义，源概率分布DZn,σ′,Ei以概率
输出的采样服从目标分布DZn,σ′.因此，离散高斯分布DZn,σ′的标准方差满足σ′=τΔ，且期望的重复次数为
4.3 方案性能分析
通过第2节分析可知，只要设置σ′=τ×Δ=2τn1.5σ2，即可以利用拒绝采样技术完成加密过程.如表1所示，RS.KDM.PKHE方案中σ′从BV的KDM.SKHE和KDM.PKHE方案中σ2的超多项式倍2ω(log n)×σ2降低为σ2的多项式倍poly(n)×σ2,大大约减了的σ′的规模.根据解密正确性要求，密文模数q的规模从2ω(log n)×σ2×t降低到poly(n)×σ2×t，有效约减了密文规模，提升了同态运算的效率.
Table 1 Parameter Setting
表1 参数设置
Schemeσσ'tqKDM.SKHE[9]2ω(logn)2ω(logn)×σ2>σn2ω(logn)×σ2×tKDM.PKHE2ω(logn)2ω(logn)×σ2>σn2ω(logn)×σ2×tRS.KDM.PKHE2ω(logn)poly(n)×σ2>σnpoly(n)×σ2×t
4.4 循环安全的公钥同态加密方案
4.1节中RS.KDM.PKHE方案关于度为2的多项式满足循环安全性，在这里我们将其扩展为关于度为d的多项式满足循环安全性的方案.令
为Rt上度为d的多项式集合，即
为了实现对私钥sk的多项式p(sk)的KDM安全性，将标准的FHE密文(c0,c1)扩展为(c0,c1,…,cd)，其中d为多项式p(sk)的度.
1) KDM.PamameterSet.令λ为安全参数.选择素数q,t∈ZZ[x],以及多项式环Rq=Zqf(x)上的离散高斯分布DZn,σ和DZn,σ′.令D为FHE方案满足密文运算的深度.令参数d≤D为FHE方案满足KDM安全性的私钥函数的度.Rt为方案的明文空间.
2) KDM.KeyGen(1λ).随机选择a0∈Rq，从离散高斯分布采样得到s,e0←DZn,σ，计算b0=a0s+te0，输出私钥sk=s和公钥pk=(a0,b0).
3) KDM.Enc(pk,m).对于消息m∈Rt,按照如下方式生成密文
① 计算ai=a0vi+tei，其中vi,ei←DZn,σ.
② 采样
重复采样并以概率
计算
得到d个二元组：
③ 计算对m加密后的密文：
c0=b1+m,
ci=bi+1-ai,i=1,2,…,d-1,
cd=-ad.
4) KDM.Dec(sk,c).令s=(1,s1,…,sd),计算当时解密正确，输出：
m=c,s mod t.
5 结束语
本文基于噪声淹没技术给出了循环安全的公钥同态加密方案，并给出了安全性证明和参数设置.进一步，首次将拒绝采样技术引入到循环安全的同态加密方案构造方法中，给出了优化的循环安全公钥加密方案，使得系统参数从超多项式级降低到多项式级，有效约减了公钥规模和密文规模.
另一方面，由于拒绝采样技术的应用，导致加密算法的计算复杂性增加，但是考虑到同态加密方案的瓶颈在于密文运算，而不是新鲜密文的生成算法，而我们的方案将密文规模从超多项式级降低到多项式级，因此，可以有效降低密文运算的计算复杂性.总体而言，基于拒绝采样技术构造的循环安全性同态加密方案具有良好的性能.
[1]Gentry C. Fully homomorphic encryption using ideal lattices[C] //Proc of the 41st Annual ACM Symp on Theory of Computing (STOC). New York: ACM, 2009: 169-178
[2]Gentry C. A fully homomophic encryption scheme[D]. Stanford, CA: Stanford University, 2009
[3]Boneh D, Halevi S, Hamburg M, et al. Circular-secure encryption from secision Diffie-Hellman[G] //LNCS 5157: Advances in Cryptology (CRYPTO 2008). Berlin: Springer, 2008: 108-125
[4]Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the Association for Computing Machinery, 2009, 56(6): 1-40
[5]Applebaum B, Cash D, Peikert C, et al. Fast cryptographic primitives and circular-secure encryption based on hard learning problems[G] //LNCS 5677: Advances in Cryptology (CRYPTO 2009). Berlin: Springer, 2009: 595-618
[6]Yang Xiaoyuan, Zhou Tanping, Zhang Wei, et al. Application of a circular secure variant of LWE in the homomorphic encryption[J]. Journal of Computer Research and Development, 2015, 52(6): 1389-1393 (in Chinese)(杨晓元, 周谭平, 张薇, 等. 具有循环安全性的同态加密方案设计[J]. 计算机研究与发展, 2015, 52(6): 1389-1393)
[7]Zhao Xiufeng, Mao Hefeng, Liu Shuai, et al. Analysis on matrix GSW-FHE and optimizing bootstrapping[J]. Security and Communication Networks, 2018, 12, DOI: 10.1155/2018/6362010
[8]Hiromasa R, Abe M, Okamoto T. Packing messages and optimizing bootstrapping in GSW-FHE[G] //LNCS 9092: Proc of Int Workshop on Public Key Cryptography (PKC 2015). Berlin: Springer, 2015: 699-715
[9]Brakerski Z, Vaikuntanathan V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[G] //LNCS 6841: Advances in Cryptology (CRYPTO 2011). Berlin: Springer, 2011: 505-524
[10]Micciancio D, Regev O. Worst-case to average-case reductions based on Gaussian measures[J]. SIAM Journal on Computing, 2007: 37(1): 267-302
[11]Goldwasser S, Kalai Y T, Peikert C. Robustness of the learning with errors assumption[C] //Proc of Symp on Innovations in Computer Science 2010. Beijing: Tsinghua University Press, 2010: 230-240
[12]Lyubashevsky V, Micciancio D. Generalized compact knapsacks are collision resistant[C] //Proc of Int Colloquium on Automata, Languages & Programming. Berlin: Springer, 2006: 144-155
[13]Stephens-Davidowitz N. Discrete Gaussian sampling reduces to CVP and SVP[J]. Computer Science, 2016: 1748-1764
[14]Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[G] //LNCS 6110: Advances in Cryptology (EUROCRYPTO 2010). Berlin: Springer, 2010: 1-23
[15]von Neumann J. Various techniques used in connection with random digits, national bureau of standards[J]. Applied Math, 1951, (12): 36-38
[16]Lyubashevsky V. Lattice-based identification schemes secure under active attacks[G] //LNCS 4939: Proc of Int Workshop on Public Key Cryptography (PKC 2008). Berlin: Springer, 2008: 162-179
[17]Ducas L, Durmus A, Lepoint T, et al. Lattice signatures and bimodal Gaussians[G] //LNCS 8042: Advances in Cryptology (CRYPTO 2013). Berlin: Springer, 2013: 40-57
ciency of the scheme. However, the size of the public key can be made independent of the circuit depth if the somewhat homomorphic scheme can securely encrypt its own secret key. Achieving circular secure somewhat homomorphic encryption has been an interesting problem which is worth studying. This paper presents a circular secure public key homomorphic encryption scheme using noise flooding technique, and gives the security proof and parameter setting; furthermore, by introducing the refuse sampling technique, an optimized circular secure public key homomorphic encryption scheme is given, and the system parameters are reduced from the super polynomial level to the polynomial level, which greatly reduces the public key and ciphertext size. And then the computational complexity of ciphertext evaluation can be effectively improved and the performance of homomorphic encryption scheme be improved.
