毕业论文（设计）整数上的全同态加密方案及相关问题研究.pdf

中文摘要中文摘要 丫23237g密码学领域中的全同态加密最早被称为秘密同态加密，由Rivest、Adleman 及Dertouzos于1978年提出.其基本思想是直接对密文进行运算，所得结果与先 对明文进行同样运算再加密的结果相同.因此全同态加密技术使人们可以直接对 加密数据进行检索、比较,而在整个运算过程中无需对加密数据进行解密.然而全 同态加密技术的构造问题一直是密码学中的一个重要的悬而未决的公开问题直 到2009年Gentry在其博士论文中提出了第一个全同态加密方案的构造方法,解 决了这一重要的密码学难题.本文主要对基于整数的全同态加密方案进行了研究，具体工作如下：(1)对Gentry的基于理想格的全同态加密方案进行了详细的分析，包括Somewhat 同态加密方案、Tweaked的Somewhat同态加密方案和Gentry的压缩自举 方案.并通过将该方案与其它全同态加密方案进行比较,指出该方案存在的不足之 处.(2)对Dijk等人提出的整数上的全同态加密方案进行了分析，进而提出了 一个具有较小公钥尺寸的全同态加密方案，使公钥由pk=(o,.)变 为pk=(3卢1),公钥尺寸由0(*。)降至O(A3),并对安全性及噪声进行了分析.(3)在较小公钥全同态加密方案的基础上,通过将原方案中的模2运算推广到 模2k运算，构造出了一个多比特加密的全同态加密方案，该方案可以一次性同时 加密k比特明文,在降低方案公钥尺寸的同时进一步提高了方案的加密速度.关键词：密码学;全同态加密；整数；理想格黑龙江大学硕士学位论文AbstractIn the field of cryptography,fully homomorphic encryption is the earliest known as privacy homomorphic encryption which proposed by Ri vest,Adleman and Der-touzos in 1978.The basic idea of fully homomorphic encryption is to directly operate on the ciphertext,obtained result is the same as the result of re-encryption after the same operation on the plaintext.So fully homomorphic encryption technology can make people directly to retrieve and compare the encrypted data without having to decrypt the encrypted data in the entire operation process.Yet the structural problems of the fully homomorphic encryption technology is always a central open problem in cryptography,until 2009 Gentry put forward the method to construct the first fully homomorphic encryption scheme in his doctoral thesis,and solving the important problem in cryptography.This article mainly studied the fully homomorphic encryption scheme which based on integers,whose specific works are as follows:(1)Fully homomorphic encryption scheme based on ideal lattices are analyzed in detail,including somewhat homomorphic encryption scheme,a tweaked somewhat homomorphic encryption scheme and the squashed bootstrappable scheme of Gentry.And through the solution comparing with other fully homomorphic encryption scheme,point out the deficiency existing in the scheme(2)We investigated fully homomorphic encryption scheme over the integers which proposed by Dijk et al,and then propose a fully homomorphic encryption scheme with small public key sizes,which makes public key by pk=(如%t)to pk=(xo)i)i public key size by O(A10)down to O(A3),and for safety and noise are analyzed.(3)On the basis of fully homomorphic encryption scheme with small public key sizes,we extend modular 2 arithmetic of the original scheme to modular 2fcAbstractarithmetic,constructed for more than a bit encrypted fully homomorphic encryption scheme with small public key sizes,which can once plaintext encrypted k bits at the same time,reduce the scheme of public key size at the same time and further improve the encryption speed.Keywords:Cryptography;Fully homomorphic encryption;Integer;Ideal lattices一皿一黑龙江大学硕士学位论文目录中文摘要.IAbstract.II目录.IV第1章绪论.11.1 论文研究的目的与意义.11.2 国内外同类课题研究现状及发展趋势.21.3 本文的主要工作.31.4 本文的基本结构安排.4第2章基础知识及相关定义.52.1 符号定义.52.2 相关的同态密码体制.52.2.1 RSA密码体制.52.2.2 ElGamal 密码体制.62.2.3 PMllier 密码体制.72.3 全同态加密的相关定义.72.4 本章小结.9第3章基于理想格的全同态加密方案的研究.103.1 理想格的相关理论知识.103.2 Gentry的全同态加密方案的研究.113.2.1 Gentry的Somewhat同态加密方案.113.2.2 Tweaked 的 Somewhat 同态加密方案.123.2.3 Gentry的压缩自举方案.123.3 其它相关的全同态加密方案.14IV 目录3.4 本章小结.15第4章一个具有较小公钥尺寸的全同态加密方案.164.1 整数上的全同态加密方案.164.1.1 整数上的Somewhat同态加密方案.164.1.2 整数上的全同态加密方案.194.2 一个具有较小公钥尺寸的全同态加密方案.194.2.1 较小公钥尺寸的Somewhat同态加密方案.204.2.2 Somewhat同态算法、评估次数等问题的分析.214.2.3 较小公钥尺寸的全同态加密方案.244.3 本章小结.26第5章一个多比特加密的全同态加密方案.275.1 本文的基本框架.275.2 多比特加密的Somewhat同态加密方案.295.3 可评估次数的分析.315.4 多比特加密的全同态加密方案.335.5 本章小结.35结论.36参考文献.37致谢.44独创性声明.45-V-第1章绪论第1章绪论对密码学的研究与应用己有几千年的历史了，其基本目的是令通信双方能够在 一个不安全的信道上进行通信,任何第三方即使在传输过程中截获了通信内容,也 无法获得所截获内容的正确含义.但是随着科技的进步,传统的加密方案已不再安 全了，因此全同态加密技术的出现是必然的.1.1 论文研究的目的与意义全同态加密方案的构造方法长期以来一直是密码学中的一个重要公开问题，自 该问题被提出后的30余年来，一直困扰着密码学家们.2009年Gentry在其博士 论文中提出了第一个基于理想格的全同态加密方案的构造方法,开启了全同态加 密思想的新篇章.全同态加密是在不对密文进行解密的情况下,直接对密文进行运 算，其结果与直接对明文进行同样运算得到的结果相一致.全同态加密思想的出现，使信息的传输更为安全可靠,而不再担心会被不可信服务器泄露消息.以前所涉及 的同态加密方案要么满足加法同态，要么满足乘法同态，而全同态加密方案是既满 足加法同态又满足乘法同态的加密方案，在确保安全性的前提下使方案的计算困 难性减弱.本文对全同态加密方案进行了分析,不但涉及理想格上的全同态加密方 案，而且包含对整数上的全同态加密方案的分析，同时给出对Dijk等人提出的整 数上的全同态加密方案的改进.目的在于让大家知道全同态加密方案的构造不仅 仅可以建立在理想格的数学背景下，而且在其他更为简单的代数背景下，实现起来 更为方便、快捷.本文主要对整数上的全同态方案进行研究，首先对基于理想格的全同态加密方 案进行总结，概括出全同态加密方案的构造框架，由于其理论难度大、不易理解,因此Dijk等人提出了理论结构简单的整数上的全同态加密方案.本文对Dijk等 人的整数上的全同态加密方案进行分析，其目的在于让人们对全同态加密的发展 现状有更加详细的了解；在Dijk等人的整数上的全同态加密方案的基础上，构造 出了一个具有较小公钥尺寸的全同态加密方案，使公钥由p=（co,q,，勺）变 1 黑龙江大学硕士学位论文为pk=（工0#1）,公钥尺寸由d（A10）降至0（A3）;最后在较小公钥尺寸全同态加密 方案的基础上,通过将原方案中的模2运算推广到模2k运算，构造出了一个多比 特加密的全同态加密方案,使该方案由单比特加密推广到多比特加密.1.2 国内外同类课题研究现状及发展趋势1978年，Riveset Adleman和Dertouzos继RSA公钥密码体制国之后，第一 次提出了秘密同态的概念也开启了同态加密研究的先河，使同态加密的研究进入 了崭新的时代.1984年，第一个基于离散对数困难问题的公钥加密体制ElGamal加密体制网 被提出，它是满足乘法同态的密码体制.ElGamal体制亦被称为乘法同态加密体 制，支持任意多次乘法同态运算.在同一年Goldwasser和Micali首次提出了概 率加密M的思想，给出了语义安全性的概念，提出了 GM公钥密码体制.它是加 法（模2）的同态加密体制，支持任意多次加法（模2）同态运算,这是一个具有语 义安全性的同态加密方案.1994年，针对GM体制每一次加密智能处理1比特信息缺陷的文问题,Benaloh提出了一种新型的概率同态加密体制，它仍然是保持加法同态运算的加 密体制,但是它只能支持有限次加法同态运算.1998 年，Okamoto 和 Uchiyama、Naccache 和 Stem 分别提出 0U 体制问 与NS体制叫两者均属于加法同态运算,都能支持任意多次加法同态运算.1999年,Paillier体制被提出，它是第一个基于判定合数剩余类问题的加法 同态密码体制，支持任意多次加法同态运算.2001年,Damgard和Jurik提出了 DJ体制叫它是对Paillier体制的推广，仍 然可以支持任意多次加法同态运算.2005年，Boneh、Goh与Nissim提出了 BGN同态加密体制【叫 该体制可以 同时支持任意多次加法同态运算和一次乘法同态运算.该密码体制是同态加密问 题提出近30年来，与全同态加密方案构造最相近的一个同态加密体制.但是另一 方面，如何使该方案实现全同态加密的过程又是那么遥不可及.第1章绪论在此期间密码学家一直寻找构造全同态加密方案的方法,涌现出大量关于同态 加密的构造方案,包括实数范围上的网和格上的1啕，同时还出现一些其它的关于 同态加宓方案的研究口3一词及应用16-181的方案,但是都无法达到全同态的要求.2009年,全同态加密构造问题出现重大技术突破,Gentry在基于理想格的基础 上构造出第一个全同态加密方案2加L近30年来悬而未决的一个重要公开密码问 题得到了解决,使全同态加密的研究进入新的纪元.2010年,Smart和Vercauteren对Gentry构造方案进行了改进,提出了一种具 有更短密钥与密文长度的改进方案1列,使其在效率上有一定的提高.同一年Stehle 和Steinfeld提出了对其的另一种改进方案【冽，降低了方案对安全参数A的依赖 性.2010年，Dijk等人提出了整数上的全同态加密方案必叫使理论背景由较难理 解的理想格变成简单的整数范围上,其最大的优点是理论结构简单.此后密码学家分别在欧密会、亚密会等几大密码学会议上,提出了大量的关于 理想格上的侬一切、整数上的冲-31)以及 加 上的阳-到全同态加密方案的分析 及改进附-421.国际上对全同态加密技术的研究还局限在对Gentry原始方案的改 进、优化和计算机实现等几个方面上，而具体应用方向的研究I43-48则还在探索 中，具体的实现方案实例几乎为零.国内关于对全同态加密方案研究的文献数量非 常少，而且同样是基于Gentry方案基础上进行研究的，现存的几篇文章均是对整 数上的全同态加密方案的分析及改进Mt】).1.3 本文的主要工作首先，对Gentry基于理想格的全同态加密方案进行分析，从Somewhat同态 加密到全同态加密的具体构造思想给予解释，并与其它同类文章进行比较分析.其次，对Dijk等人的基于整数上的全同态加密方案进行研究，并在其基础上 进行改进，进而提出具有较小公钥的全同态加密方案，使公钥尺寸由O(A10)降 至 O(A3).最后,在较小公钥全同态加密方案的基础上，将原方案中的模2运算推广至-3 黑龙江大学硕士学位论文模2A运算，从而构造出一个一次性加密k比特明文的多比特加密方案.1.4 本文的基本结构安排本文的结构安排如下：第1章绪论，主要介绍了全同态加密的发展背景，同态加密方案的国内外研究 现状,及方案研究的目的意义.第2章同态加密的相关知识，主要介绍与本文相关的密码学知识,为以后的方 案预备基础知识.第3章通过对基于理想格的全同态加密方案的研窕,概括出全同态加密方案的 理论框架,使人们对全同态加密方案的构造过程有进一步的了解.第4章通过对整数上的全同态加密方案的分析,进而提出一个具有较小公钥尺 寸的全同态加密方案,使公钥尺寸由。(*)降至0(A3).第5章在较小公钥尺寸的全同态加密方案的基础上进行改进,构造出一个多比 特加密的全同态加密方案，使该方案由单比特加密推广到多比特加密.4-第2章基础知识及相关定义第2章基础知识及相关定义本章主要介绍与本文相关的符号与定义.2.1 符号定义给定一个实数Z,M表示向上取整，即z e忆Z+1)；z表示向下取整，即W(z-1,4区表示取其最近的整数，1X1 W(Z l/2,z+1/2.给定一个实数z和一个整数P,用温z)表示Z除以p的商,rp(z)6(-p/2,p/2 表示z除以p的余数，即qp(z)=z/p,Tp(z)=z-%(z).p;也可以用zp或21nodp 表示4(z).2.2 相关的同态密码体制在全同态加密出现以前，所有的同态加密体制都仅仅是满足加法同态或乘法同 态的加密体制，下面简要介绍这类相关的同态加密体制.2.2.1 RSA密码体制RSA密码体制禺是由Rivest、Shamir及Adleman提出的第一个实用的公钥 加密体制，其安全性是基于大整数分解的困难性，具体构造如下：参数选取：为了生成两个密钥sk和pk,随机选取两个大的素数p和q.为了 保证最大限度的安全性，则必须确保p,g具有相同的长度，并计算乘积n=的，欧 拉函数(n)=(p-l)(g 1).然后随机生成加密密钥e,使得gcd(e,(n)=1,计 算e关于模 枷)的乘法逆元d,即ed=lmod(n).返回公钥为pk=(n,e),私钥 为就=d.计算过程中不再需要p和q,但必须保密，它们的作用只是用来产生e 和d.-5-黑龙江大学硕士学位论文加密：对明文m进行加密，输出密文E(m)=znmodn.解密：对密文c进行解密，得到明文。=Imodn.RSA加密体制满足乘法同态性质：对明文 g：m2 加密，有 6=m；modn,C2=m5modn,贝UE(mi)E(m2)=(mf modn)(m5modn)=(m)(m2)modn=(mim2)cmodn=(17117712)即E(m】)E(m2)=即RSA加密体制满足乘法同态运算.2.2.2 ElGamal密码体制ElGamal密码体制同是第一个基于离散对数问题的公钥加密体制，其安全性 是基于离散对数问题的困难性，具体构造如下：参数选取：随机选取一个素数p,g是循环群z；的生成元,在循环群z；中随机 选取一个元素x,计算y=modp.公钥pk=e,g,p),g和p可由一组用户同时 拥有，私钥sk=x,加密：随机选取一个整数k、使gcd(A,p-1)=1,生成密文E(m)=(a,b)=(gkmodp,t/*mmodp).解密：明文 m=b(ax)-1modp.ElGamal具有乘法同态加密性质：对明文 g、m2 加密,有 顼mi)=(ai,6i)=(felmodp,/gmodp),E(m2)=(02,电)=(gmodp/m2modp).若定义 E(m2)=(。1。2,打电)，则有E(mi)0 E(m2)=(gk】+*3modp,卢+77117712modp)其中 k=h+=mim2,则;(mi)E(m2)=E(mi?n2),即满足乘法同态性质.6 第2章芈础知识及相关定义.2.2.3 Paillier 密码体制PailMer密码体制同于1999年被提出，其安全性是基于判定合数剩余问题的 困难性,PaiUier密码体制是具有语义安全性的加法同态加密方案.具体方案描述如 下：参数选取：随机选取两个素数p,q令n=的，且几满足gcd(n,0(n)=1,随 机选取 g G 满足 gcd(L(gAmodn2),n)=1,则公钥 pk=(n,g),私钥 sk=lcm(p-1),(g-l),m 为明文.加密：随机选取整数r e Z；,对明文m加密为E(m)=gmrnmodn2.解密:对密文E(m)解密,可通过下面的式子计算出明文m,Lfcmodn2)m”而彘润modn其中力=匕上 nPaiUier密码体制具有加法同态性质：对明文加】,利加密，有E(m)=mirymodn2,E(m2)=grmodn2,有E(mi)E(m2)=(gmirJmodn2)(pmir；modn2)=gmi+m2(r i r2)modn2=E(m+m2)即满足加法同态性质.2.3 全同态加密的相关定义全同态加密体制是指对密文进行一定的运算，与对明文直接进行同样的运算 后再加密得到的结果是相同的.在本节中我们回顾相关同态加密的定义，都是基 于河中的定义.定义2.1同态加密方案算法由以下四个算法构成:l.KeyGen:已知安全参数A,返回私钥sk和公钥pk.7 黑龙江大学硕士学位论文2,Encrypt:已知明文m e 0,1公钥pk,返回密文c.3.Decrypt:已知密文c和私钥sk,返回明文m.Evaluate:已知公钥pk,t个输入的电路C(由模2的加法门与乘法门构 成的布尔电路)、一组密文c=(ci,.，q),其中G=Encryptk.mi),返回密 文 c*=Evaluate(pk,C.c),且满足 Decrypt(sk,c*)=C(thi,.,mt).定义 2.2(正确性)方案 =(KeyGen,Encrypt,Decrypt.Evaluate)对 t 个 输入的电路C满足正确性的必要条件是:对于任意的安全参数A,KeyGen(X)输 出的任意密钥对(sktpk)f给定任意明文加：.,啊 与对应的密文d=,.，q),其中 Ci Encrypt(pk.m.若 c*=Evaluate(pky C,c),则必有 Decrypt(sk,c*)=定义 2.3(紧凑性)方案 =(KeyGen,Encrypt,Decrypt,Evaluate)是紧凑 的,需满足以下限制条件：对于任意给定安全参数3 KeyGen(X)输出的任意密 钥对(pk.sk),对于任意电路CwCg,给定任意明文 啊,g,，恤 与对应的密 文=(C1,C2,-yCt),其中 Ci-Encrypt(pk,mi),c*0,对于所有的ij,有%6 号掾).已知L的任意基B,由高斯消 去法能有效计算出HNF(L).HNF(L)能使L上的基泄露最少的信息.因此把它作 为公钥的表达方式.令Zx是一个首一 n次不可约多项式.在本篇文章中,用/(x)=俨+1表 示，其中n是2的方嘉.令R表示多项式环Zx/(x),即R=Z/.R中每个元 素都是次数至多为n-1的多项式.因此其系数向量在中，由此可知R中每个元 素既是多项式又是向量.对于V(x),令|V|是其系数向量的欧几里得范数，对于 每个环凡有一个扩展的乘法因子7MH存在，使得|ux训 加山(初训|训,其中“x”表示环中的乘法.当/(I)=F+1时,tmw(R)=然而,对于随机 向量iv的扩展因子要比回小的多，通常取|u x训。间.|训.令I是R的理想，且/是H中的元素在加法、乘法下封闭的子集.由于I是 加法封闭的，所以与/中元素有关的向量在格中.我们称I是理想格，着重强调其 作为代数理想与格的双重性质.理想有作为格的加法结构，也有乘法结构./与J 10 第3章基于理想格的全同态加密方案的研究两个理想的乘积IJ是一个封闭的集合：D x W:V W八W 6 J,其中“X”是环 中的乘法.3.2 Gentry的全同态加密方案的研究2009年,Gentry提出了第一个基于理想格的全同态加密方案,解决了重大技术 问题.该方案可以对任意深度的电路进行计算，其构造思想为：首先使用理想格的 数学工具构造出一个可以对低次多项式进行评估运算的Somewhat同态加密方案；然后给出了一种将该方案修改为具有“自举”的性质.特别的通过对Somewhat同 态加密方案的修改方法,使得其具有自解密功能，即需要有“自引用的性质”；最后，通过自举转换成为全同态加密方案.3.2.1 Gentry的Somewhat同态加密方案首先对Gentry的Somewhat同态加密方案进行分析，其支持有限次的乘法同 态.在下述方案中，对于首一的不可约多项式/,产生的密文是在环R=Z.在密钥生成阶段生成两个素理想/和J,理想/中有基Bi.为了使方案简 单，文中假设理想I=(2):Vmod/的归约与Vmod2的系数归约相一致.理想J 是由IdealGen算法产生的，已知(A,n),IdealGen生成一个好的私钥基B%并计 算其自身的HNF以便获得一个环的公钥基8%方案构造如下：KeyGen(X):由IdealGen(X,n)生成密钥对(BRB号).对于理想/使 得。(8寸)包含以圆点为中心半径为7Dec Ai(J)的球，其中Ai(J)为格L 中最短非零向量的长度,返回pk=琢,sk=Bf.Encrypt(pk,%):已知明文 m E 0,1、公钥 pk,执行 t/7r+/,|%|7Enc,返回“=nmodBj.Decrypt己知密文协和私钥sk,返回开=modBjk.E”QEae(pk,C,(矽i,，仇):已知公钥pfc,电路C和密文 如，仇,对于每 一个C中的加法门或乘法门密文耽，物执行Rmodi叶上的+或x操作，返 回运算结果.-11 黑龙江大学硕士学位论文明文空间为P(/)的子集，假设7T 0,1.为了对明文%加密，利用Samp算 法从陪集7T+1中抽取7T+计算矽=(7T+假设rEnc Dec,因此通过利用WmodB空的归约来恢复开+3那么万可由的归约来恢复.3.2.2 Tweaked的Somewhat同态加密方案在Somewhat同态加密方案引进了“Tweaked”是为了简化解密算法，改进后 的方案与原来方案的不同在于密钥生成与解密阶段,具体分析如下：KeyGen(X):调用Somewhat同态加密方案中的IdealGenX,n)生成密钥 对(8，,B牛).根据B手、计算向量尸，使得。(。(b尸)包含半径 为4ec=亨、的球，返回公钥Pk=理和私钥sk=Bp8v2n2-5Decrypt(sk*):已知密文矽和私钥sk,返回？r=砂一 Vjk x*.引理3.1密文”=(万+i)modBf其中|%+i|r屋.由Decrypt能正确 解密出7T.此外若|忱+|L那么的系数为某一整数的OC是由两个输入、一个输出的模2加法门与乘法门构成的，g(C)表示由环R 中的与“x”代替模2加法门与乘法门电路获得的.若对于任意的g(C)输入集 合7T1,有加|3其中k=1,/有g(C)(7Tl,，取)4 7屋,那么 称g(C)为允许电路.允许电路是能对明文g,的同态加密进行评估的电路,产生一个密文协=g(C)Si+，】,，7Tt+)modB已正确解密后为。(小，：看)并使得外七x砂的系数为某一整数的O引理3.2令C是模2的布尔电路,g(C)表示环R中的生成电路,对d次的 函数h蜀工】,m进行评估.若褶一】|可|,711c 7屋,那么C是允许电路.特 别的假设h的系数在0,1内，满足如下条件则C是允许电路.d，SqHom的密文(W；，左)能由Ded正确 解密,并且k SkCk为某一整数的其中砂=(7T+)m。烟t忖+ill 7展KeyGen(X):运用KeyGen生成B芋与VJk.生成一个唯一的X比特长的 向量s=(si：，s*),其中8的汉明重量为r*且si=L根据 生成N-1个均匀独立的向量h,/-，计算L=厅一 Eks山.返 回 sk=或 pk=(Bj*;公Enc(pk):调用上述方案中的加密算法获得密文砂计算ckyk=1,2,.,X)使得|q-限x仙mod2|2?其中回。表示多项式g E R的常数项，返 回(4;6,ZW(sk,(矽;5 Cr“i)：已知扩展密文(矽;6,，._1)和私钥sk,返 回斤=Mo-0上5比凝.Eval:已知公钥pk,t个输入的电路C和密文丸场，仇,对于每一个电 路C中加法门或乘法门执行RmodBk上的或运算,输出运算结果.定理3.4 任意一个自举型同态加密方案均可转化成全同态加密发案*.使用解密电路压缩技术可以使一个自举型同态加密方案转化成全同态加密发 案，其中最重要的步骤是Recrypt重加密的过程.在Gentry的构造方案中，以及后 面提到的DGHV构造方案中，密文包含一个随机噪声，随着同态次数的增加，噪声 量也逐渐增加，当达到一定范围时，密文不能被正确解密，限制了同态操作的次数,因此引入了 Recrypt算法.Recrypt算法通过对密文进行“刷新”控制噪声的增量.己知明文7T对应密文R计算7T的另外一个密文并且满足密文小的噪声小于 密文S所带有的噪声.通过对密文进行周期更新，就可以对任意电路进行计算Recrypt算法通过对密文进行同态加密来实现,假设明文7r在加密公钥由作 用下的密文次.假设存在另一个加密公钥pk2,并且存在使用pk2加密后的解密密 钥 ski,记为 函=Encrypt(pk2t ski).Recrypt 算法如下：Recrypt(pk2,D,s%底):对于明的每一个比特耽力生成可=(P%矽u)；记寸=,输 出矽一Evaluate(j)k2 D,/).-13 黑龙江大学硕士学位论文Recrypt算法实际上是连续对明文7T进行两次加密，第一次使用加密公钥pfci,第二次则使用加密公钥诉2,而后采用Evaluate算法对第一次加密的密文进行解 密.一般情况下，对于一个公钥加密方案而言，对这样一个二次加密过程进行解密 的过程必须是：首先对第二次加密的密文解密，而后再对第一次加密的密文解密.但是Recrypt算法的一个特别之处在于它能直接对第一次加密的密文进行解密运 算.因此运用Recrypt算法进行递归调用，就可以构造出一个全同态加密方案.3.3 其它相关的全同态加密方案2010年,Smart和Vercautem在PKC会议上提出了具有相对小密钥和密文长 度的全同态加密方案阳），是在Gentry方案基础上改进的.利用判别式为素数的主 理想格进行构造，且本方案中的主理想格能被两个整数表示.他们对Gentry方案 中的Somewhat同态加密阶段进行优化,但是找不到足够大的参数使Gentry的压 缩技术能进行下去，因此不能得到自举的或全同态的加密方案.在Smart和Vercauteren的优化方案中最大的阻碍是，Somewhat同态加密阶 段密钥生成算法的计算复杂度.首先要想找到一个判别式是素数的主理想格,必须 产生很多候选的格，即使我们找到了一个符合条件的主理想格，这个格相对应的私 钥的计算复杂度至少是n维格的甘（心5）.由于这两个原因，我们不可能生成维 数n 2048的密钥.此Smart和Vercauteren做出如下估计：压缩解密多项式的次数是成百的，为 了支持这个程序的参数需要至少使用维数为n=227的格,这就超出了密钥生成算 法的能力.在Gentry和Halevi的方案中与Smart和Vercauteren的方案所研究的 方向一致,并且压缩程序是成立的，因此获得一个自举方案和全同态方案.2010年,在亚密会上提出了一个较快速的全同态加密方案，其理论背景也是在 理想格上以允许可忽略概率解密错误的存在,对Gentry方案进行了优化提出了一 个较快速的全同态加密方案.主要是从两点进行改进的，一是降低了稀疏子集和问 题上的向量个数；二是降低解密多项式的次数,但同时导致了解密错误概率的增加,因此在之后的优化方案中，我们只考虑第一个优化思想.一 14 一第3章基于理想格的全同态加密方案的研究2011年，在欧密会上Gentry和Halevi提出了一个全同态加密的实现方案，是 对Smart和Vercauteren的优化.主要是对Somewhat同态加密方案中密钥生成 算法的优化,使方案的复杂度由。(入嫣)降到d(A15).在方案中利用进位加法代替 了原方案中的hree4or-two”技术,使方案实现起来更容易.现存的对Gentry方案的优化方案都是在理想格的理论背景下进行研究的，且 主要是从参数、运算复杂度等角度进行改进的，目的在于使方案的运算效率有所 提高.3.4 本章小结在本章中,首先是对Gentry基于理想格的全同态方案的分析,从Somewhat同 态加密方案到全同态加密方案做了系统的介绍，总结出全同态加密方案的构造框 架跃，使人们对全同态加密方案有进一步的了解;然后是对其改进方案进行了分析,使人对基于理想格的全同态加密方案有更深的理解.15 黑龙江大学硕士学位论文第4章一个具有较小公钥尺寸的全同态加密方案理想格上的全同态加密方案的理论性较强,不易理解而且构造困难，因此简单 代数上的全同态加密方案的提出是必然的，本章主要对整数上的全同态加密方案 进行分析及改进.4.1 整数上的全同态加密方案为了使全同态加密方案的构造方法更容易理解，按照Gentry的思想，基于近 似最大公因子困难问题，Dijk等人提出了概念上更为简单的整数上的全同态方 案(即DGHV全同态加密方案)并对其进行了研究.DGHV全同态加密方案的基本构造思想是：首先基于近似GCD网困难性假 设构造一个同态对称加密方案，而后通过实施一个简单变换将其变换为一个同态 公钥加密方案，而后使用Gentry所提出的构造思想与处理方法使得同态公钥加密 方案具有自举能力，进而构造出一个最终的全同态加密方案.该方案的安全性基于 近似GCD困难性假设与稀疏子集和困难假设,进而为了更详细地描述基于整数上 的全同态加密方案的可行性，Dijk等人证明了如下定理4.1,在本节中就不对其进 行证明了.定理4.1利用整数上的加法与乘法运算,基于近似GCD问题与稀疏子集和 问题的计算困难性,可以构造出安全的全同态公钥加密方案.4.1.1 整数上的Somewhat同态加密方案本小节将主要介绍Dijk等人提出的基于整数上的Somewhat同态加密方案,该方案的构造核心是：首先构造一个较为简单的Somewhat对称同态加密方案,而后将其扩展为一个Somewhat公钥同态加密方案*,具体过程如下：参数选取：令p=X,p=2人,n=O(A2),fl=A4j7=O(A5),其中A为安全参数.16 第4章 一个具有较小公铜尺寸的全同态加空方案7表示公钥的比特长度，为了防止对基于格的近似最大公因子问题的破解,公 钥长度应满足7=3g2 log A).T)表示私钥的比特长度，为了使压缩解密电路属于允许电路，因此私钥的长度 应满足 rjp-(Alog2A).p表示噪声的比特长度,为了阻止蛮力攻击(brute-force attacks)噪声长度应满 足 p=3(10gX).P表示第二个噪声的比特长度,且长度应满足p=p+u;(logA).T表示公钥的个数,应满足T7+u；(logA).(l)Somewhat对称同态加密方案利用上述给定的参数,基于整数上的平凡运算构造出如下所述的对称型同态加 密方案：KeyGen:生成一个q比特的随机整数p,令p为密钥k.Encrypt:对明文m E 0,1加密，随机选取一个整数r,使得|m+2r|p,输出密文c 1 m+2r+pq,其中q为一个7比特随机整数.Decrypt:输出(cmodp)mod2.由上述对加密方案的描述可知，方案输出的密文为p的近似倍数.在本 文中，称cmodp是与密文c相关联的噪声.实际上，噪声描述的是与p最近倍数之 间的距离.解密过程中的噪声为r,它与明文m具有相同的奇偶性，因此可以正确 解密.称加密过程中Encrypt算法所输出的密文为“刷新”密文，因为它具有较小 比特的噪音.由于选取的明文为整数，可以对被加密的消息进行简单的加法与乘法运算.但 是这样运算之后将带来一个问题:这些运算将直接导致与密文相关联的噪声变大.更重要的是如果运算次数不断增加，那么噪声最终会增大到解密过程无法正确地 解密出正确明文的程度.由整数上的平凡运算的定义可知，加密方案支持以下的同态运算:Add(“C2),Mult(c1,c2)i对应计算输出的密文分别是C1+C2.C1XC2,因此Evaluate 算法构造如下：杷(/,%,牛)：将函数/表示为一个由异或门和与门构成的电路C.-17-黑龙江大学硕士学位论文令C”是与C相同的电路,但是分别使用整数加法门与整数乘法门来代替异或门 和与门.记/,为与C*对应的多变量函数,输出c J/,，q).(2)Somewhat公钥同态加密方案目前已成功构造出了一个对称加密方窠事实上将上述方案E转化成 为Somewhat同态公钥加密方案是很容易的，只是相应的操作规则会复杂一些.为构造令解密密钥sk=p,对应的公钥则为一列整数pk=x-pg+2r.不难看出，每个整数都是“利用加密方案对零的加密。这里公钥长度是关于A 的多项式.利用对任意一比特明文m进行加密时，其对应的密文c都是m加上加密 公钥的一个随机子集和.如果密文噪声较小,那么生