全同态加密方案(Fully Homomorphic Encryption),曾被称为隐私同态,可以实现在不解密密文的情况下对密文用门电路进行处理得到一个新密文,对该新密文进行解密与对相应的明文做同样处理的结果相等。1978年,Rivest,Adleman和Dertouzous在RSA加密方案提出不久之后,根据RSA加密方案[2]是一种乘法同态的加密方案,提出的全同态的加密思想[1]：一个包括有效评估算法Evaluateε的加密方案ε,对任意有效的公钥pk,任意门电路C(不仅仅包括RSA中的乘法门电路)以及任意的密文ψi←Encryptε(pk,πi),可以输出ψ←Evaluateε(pk,C,ψ1,…，ψt),这是在公钥pk下对C(π1,...,πt)的有效加密。基于全同态的加密思想可以构造全同态加密方案实现在没有解密密钥的前提下对加密的数据进行任意计算,来保护用户的隐私。该加密方案可以有效的运用在云计算、隐私查询、物联网、电子商务等领域中,以保护用户的数据隐私。尽管全同态加密方案具有良好的性质,国内外学者也对其做了大量的研究,但所提出的方案很难做到对任意深度的门电路或任意次数多项式的处理。直到2009年,Gentry基于理想格困难问题,利用Bootstrappable思想和重加密技术构造出第一个全同态加密方案[3]。根据Gentry构造全同态加密方案的思路,越来越多的研究者不断提出新的全同态加密方案。现在的全同态加密构造方案大致分为三类[8]：第一类,Gentry基于理想格困难问题构造的最初的全同态加密方案[3]；第二类,Dijk等人提出的基于整数上运算的全同态加密方案[5],简称DGHV全同态加密方案；第三类,Brakerski和Vaikuntanathan等人提出的基于LWE和RLWE困难问题的全同态加密方案[9,10]。2010年,Dijk和Gentry等人提出了一个基于整数运算上的全同态加密方案[5],被称为DGHV方案。该方案在简单的代数结构上进行研究,完全基于整数上的基本运算,将明文的1比特加密为一个大整数。并将该方案的安全性规约到近似GCD困难问题和SSIP困难问题。2011年,Coron和Mandal等人针对DGHV方案中存在的公钥占用空间大的问题进行了改进,用二次形式生成公钥代替最初DGHV方案中线性形式的生成公钥,将所需的公钥大小从Ο(λ10)降低到Ο(λ7)[7],并将改进方案的安全性规约到基于多变量的近似GCD困难问题。2013年,Coron和Lepoint等人针对DGHV方案的密文膨胀率高的问题进行了改进,利用中国剩余定理,将多个明文比特加密为一个密文,实现DGHV方案的批处理功能[8],将DGHV方案中的密文膨胀率从0(λ5)降低到Ο(A3)本文主要针对DGHV方案的密文膨胀率问题提出另外一种改进方案,利用{0,1}k数域上的相关知识,将k个明文比特转化为(0,…,2k-1)上的整数,对整数进行加密,实现DGHV方案的批处理功能。将DGHV方案中密文形式c=q.p+2·r+m,转换为c=q.p+2k·r+m,其中p为私钥,q为一个大随机整数,r为一个小随机整数(噪音)。通过将改进方案中的安全参数λ’设置为λ+k,其中λ为DGHV方案中的安全参数,使得改进方案满足正确的同态解密,从而构造出一类整数上有效的全同态加密方案。与加密k个比特的DGHV方案相比,该改进方案可以将密文的大小从Ο(k·λ10)降低到Ο((λ+k)10),相应的公钥大小从Ο(λ10)增加到Ο((λ+k)10),私钥大小从Ο(λ2)增加到Ο(λ2+k)。