毕业论文（设计）基于格的全同态加密研究与设计.pdf

南京航空航天大学博士学位论文摘要全同态加密能够对密文进行任意计算，这一特殊性质使得全同态加密具有重要的理论意义 与实践应用价值。自1978年全同态加密提出后一直是密码学界的一个开放难题，直到2009年 Gentry设计出第一个全同态加密方案。尽管近年来全同态加密的研究不断取得进步，但是依然 面临以下一些问题：第一，全同态加密的候选方案很少；第二，全同态加密的效率不高，离实 践应用有距离；第三，全同态加密使用的安全性。格密码学可以抵抗量子计算，成为当前密码学界的研究热点。此外LWE问题和环LWE问 题上的密码方案计算简单，而且其安全性可以归约到格上困难问题，使得LWE问题和环LWE 问题上的密码学成为格密码学研究的一个重要主题。以下简称LWE问题和环LWE问题为（环）LWE问题。本博士论文开展（环）LWE问题上的全同态加密研究与设计。一方面从理论上，提出一些 更加有效的全同态加密方案以及优化方法；另一方面从实践角度，提出分析计算全同态加密具 体安全参数的方法，并且给出每个方案的具体安全参数。保证了研究的系统性与全面性。所做 工作如下：1.开展全同态加密方案具体安全参数分析方法的研究。主要研究方法与结果如下：（1）提出一个（环）LWE问题上全同态加密方案具体安全参数的方法。该方法基于 区分攻击，引入了敌手优势，能够真实的反映应用场景的安全需求。根据不同 的安全等级以及敌手优势，使用区分攻击确定最小维数n与模q之间的关系。再根据全同态加密方案的噪音增长与电路深度以及模之间的关系，计算出 电路深度、模4与维数的具体尺寸，从而获得公钥、私钥和密文的具体尺 寸。并且使用该方法对目前（环）LWE问题上全同态加密方案进行了具体安全 参数分析，并且进行了详细比较。这也是首次给出这些方案的具体安全参数，为全同态加密的实践奠定了基础。（2）提出一个噪音依赖分析的全同态加密方案分类的方法。通过对目前（环）LWE 问题上全同态加密方案的噪音增长进行详细分析，给出紧致的噪音界，从而获 得噪音增长的主要依赖项。根据该主要依赖项对目前全同态加密方案进行了分 类。分类的目的是为进一步优化方案提供指南。2.开展设计全同态加密方案的研究。主要研究如何去除全同态加密设计过程中的密钥交 换（key switching）过程，设计更加有效的全同态加密方案。主要研究方法与结果如下：（1）提出一个新的设计方法：提升维数法。使用该方法可以去除密钥交换过程，从 而提高全同态加密方案的效率。该方法分为两个步骤。第一步，通过添加一些 密文辅助项，将密文从向量提升到矩阵，得到一个密文是矩阵并且具有同态性基于格的全同态加密研究与设计的加密方案。但是由于噪音过大导致该方案无法进行密文计算。第二步，为了 使用位扩展技术约减密文中的噪音，再次使用提升维数法添加密文辅助项，得 到一个无需密钥交换的全同态加密方案。提升维数法比Gentry等人在2013年 美密会上提出的特征值和特征向量的方法（GSW13方案）更加有效。此外，提升维数法是一个通用框架，可以设计（环）LWE问题上所有无需密钥交换的 全同态加密方案。因此提升维数法具有重要的理论意义。（2）基于提升维数法设计一个NTRU型无需密钥交换的全同态加密方案。由于 NTRU方案中的密文是一个多项式，只需使用提升维数法的第二步，即将密文 从多项式提升到向量，就能获得一个无需密钥交换的全同态加密方案。止匕外，计算分析了该方案的具体安全参数，该方案是目前（环）LWE上全同态加密方 案中参数尺寸最小的全同态加密方案。（3）基于提升维数法设计一个环LWE上无需密钥交换的全同态加密方案。使用上 述提升维数法将密文从向量提升到矩阵，即可获得一个环LWE上无需密钥交 换的全同态加密方案。该方案的安全性归约到理想格上的困难问题。此外，计 算分析了该方案的具体安全参数，该方案的参数尺寸优于环LWE上同类方案 GSW13方案以及Bral2方案的参数尺寸。（4）基于提升维数法设计一个LWE上无需密钥交换的全同态加密方案。设计方法 与环上方案相同。但是该方案的安全性归约到格上的困难问题。该方案的参数 尺寸优于LWE上同类方案GSW13方案以及Bral2方案的参数尺寸。3.开展基于Binary-LWE问题设计全同态加密方案以及优化全同态加密方案的研究。研究 成果如下：（1）基于Binary-LWE问题设计一个短公钥的全同态加密方案。根据Linder和Peikert 在2010年提出的LWE上的公钥加密方案，基于Binary-LWE问题约减密钥长 度，从而约减密文计算的噪音，设计了一个短公钥的全同态加密方案。该方案 的公钥是目前LWE上全同态加密方案中公钥最短的。（2）研究使用Binary-LWE问题对噪音依赖于密钥的全同态加密方案，进行噪音控 制与优化。并且以LWE上Bral2全同态加密方案为实例，进行了改进与提高。关键词：全同态加密，格公钥密码学，（环）LWE问题，Binary-LWE问题，NTRU公钥加密方 案II南京航空航天大学博士学位论文AbstractFully homomorphic encryption(FHE)can compute arbitrary functions on encrypted data.Such feature of FHE has significance in theory and practical application.It was proposed in 1978 and became an open hard problem in cryptography community till Gentry proposed the first FHE scheme in 2009.After that the development of FHE has made great progress.However,FHE is still facing some problems as follows.First,candidate FHE schemes are few.Second,the efficiency of FHE is a big question.Third,how to ensure the security of FHE scheme.Therefore,it is important to design and improve FHE scheme as well as estimate the parameters of FHE scheme.Lattice-based cryptography is believed to be secure against quantum computers.Lattice cryptography has become one of the most fascinating areas of mathematical cryptography.Furthermore,learn with errors problem(LWE)and ring learn with errors problem(RLWE)serve as the foundation of most lattice-based cryptographic schemes because they are simple in computations and their harness are as hard as approximating several lattice problems in the worst case.LWE and ring LWE problems are called as(ring)LWE below.In this thesis,we focus on the research of FHE based on(ring)learn with errors problem.On the one hand,we propose some FHE schemes with better parameters than previous schemes as well as the optimization from the theoretical point of view.On the other hand,we present the method to estimate the parameters of FHE schemes based on(ring)learn with errors problem from the practical point of view.We give the parameters of each scheme we present.It ensure the systematic and integrity of this thesis.1.The research of estimating the parameters of FHE schemes based on(ring)learn with errors problem.Our main method and results are as follows.(1)We present a method to estimate the parameters of FHE schemes based on(ring)learn with errors problem.In order to be consistent with the practical application,we introduce the advantage of adversary.Given security level,advantage of adversary and Gaussian parameter,the minimal dimension n can be derived from modulus q using our method.Then modulus q can be estimated by the condition of correct decryption among noise growth,circuit depth L and modulus q.Given security level,advantage of adversary and Gaussian parameter,we can obtain different modulus q and minimal dimension n corresponding different circuit depth L.From above concert parameters,the size of public key,secret key and ciphertext can be obtained.We analyze the parameters of the current III基于格的全同态加密研究与设计FHE schemes based on(ring)learn with errors problem.It is the first to give these parameters.(2)According to the main item in the noise of the ciphertext,we present a method to classify the current FHE schemes based on(ring)learn with errors problem.For these schemes,we analyze the noise growth in detail in the homomorphic operations and give the tight bound of noise.2.The research of designing FHE schemes based on(ring)learn with errors problem.Our main method and results are as follows.(1)We present a method to design the FHE scheme without key switching based on(ring)learn with errors problem.This method we call it as lift method.The method is general.The method shows that the FHE scheme without key switching can be achieved without approximate eigenvector method(Gentry proposed in Crypto 2013).Thus the lift method has significance.(2)We present a FHE scheme without key switching based on NTRU encryption scheme.The parameters size of this scheme is smallest among all current FHE schemes.(3)We present a FHE scheme without key switching based on ring learn with errors problem.The parameters size of this scheme is smaller than GSW13 scheme on ring learn with errors problem.(4)We present a FHE scheme without key switching based on learn with errors problem.The parameters size of this scheme is smaller than GSW13 scheme on learn with errors problem.3.The research designing FHE schemes based on binary learn with errors problem as well as the optimization.Our contributions are as follows.(1)We present a FHE scheme with short public key based on binary learn with errors problem.The public key of this scheme is the shortest among all current FHE schemes based on learn with errors problem.The parameters size of this scheme is smaller than Bra 12 scheme.(2)We present an optimization to reduce the key size with binary learn with errors problem so that the noise growth can be control.We improve the Bra 12 scheme with this optimization.Keywords:Fully homomorphic encryption,lattice-based cryptography,(ring)learn with errorsproblem,NTRU public key encryptionIV南京航空航天大学博士学位论文目录第一章绪论.11.1 全同态加密引言.11.2 全同态加密思想.31.3 格密码学介绍.51.4 本文的主要研究工作.51.5 本文的内容安排.6第二章基础知识.82.1 密码学简介.82.2 数学基础知识.82.2.1 向量空间简介.82.2.2 矩阵和行列式的一些重要概念.102.3 格理论基础.112.3.1 格定义及性质.112.3.2 格上的计算问题.132.4 构建格公钥密码系统的方法.152.4.1 格公钥密码系统的框架.152.4.2 随机格.162.5 LWE问题及其公钥密码方案.172.5.1 LWE 问题.172.5.2 基于LWE的公钥加密方案.182.6 环LWE问题及其公钥密码方案.202.6.1 环 LWE 问题.202.6.2 基于环LWE的公钥加密方案.21第三章全同态加密的噪音依赖分析与安全参数分析.233.1 全同态加密定义与关键技术.233.1.1 全同态加密定义.233.1.2 全同态加密关键技术.243.2 基于噪音依赖分析的全同态加密方案研究.27V基于格的全同态加密研究与设计3.2.1 噪音依赖分析方法.273.2.2 噪音增长依赖于密文中噪音的全同态加密方案:BGV方案.283.2.3 噪音增长依赖于密钥的全同态加密方案:Bral2方案.323.2.4 噪音增长依赖于密文的全同态加密方案：GSW13方案.373.2.5 方案参数尺寸与噪音增长分析比较.393.3.1 具体安全参数分析方法.413.3.2 Bral2方案和GSW13方案的具体安全参数.433.4 总结.46第四章使用提升维数法设计NTRU型无需密钥交换的全同态加密方案.474.1 问题的提出.474.2 解决问题的主要思想.484.3 提升维数法.494.4 环LWE上NTRU基本加密方案与扩展加密方案.504.4.1 判定小多项式比问题.514.4.2 NTRU基本加密方案.514.4.3 NTRU扩展加密方案.524.5 同态属性.534.5.1 NTRU基本加密方案的同态性.534.5.2 扩展加密方案的乘法同态属性.544.5.3 扩展加密方案的加法同态属性.554.6 密文同态计算的噪音分析.554.6.1 加法噪音分析.554.6.2 乘法噪音分析.554.6.3 乘法计算优化.564.7 层次型全同态加密方案.564.8 选择具体安全参数.574.8.1 方案的参数属性.584.8.2 具体参数.584.9 总结.59第五章 使用提升维数法设计（环）LWE上的无需密钥交换的全同态加密方案.615.1 问题的提出.61VI南京航空航天大学博士学位论文5.2 解决问题的主要思想.615.3 提升维数法.635.4 密文是矩阵的环LWE上的加密方案.635.5 环LWE上扩展加密方案.645.6 环LWE上扩展加密方案的同态属性.665.6.1 加法同态性.665.6.2 乘法同态性.675.7 密文同态计算的噪音分析.675.7.1 加法噪音分析.675.7.2 乘法噪音分析.675.8 环LWE上扩展加密方案上的层次型全同态加密方案.685.9 密文是矩阵的LWE上加密方案.695.10 LWE上扩展加密方案.705.11 LWE上扩展加密方案的同态属性.725.11.1 加法同态性.725.11.2 乘法同态性.725.12 密文同态计算的噪音分析.725.12.1 加法噪音分析.725.12.2 乘法噪音分析.735.13 LWE上扩展加密方案上的层次全同态加密方案.735.14 选择具体安全参数.745.14.1 方案的参数属性.745.14.2 具体参数.755.15 总结.77第六章一个基于BINARY-LWE的全同态加密方案.796.1 问题的提出.796.2 解决问题的主要思路.796.3 Binary-LWE 问题.806.4 改进的基本加密方案.806.5 方案的同态属性.826.5.1 加法同态性.82VII基于格的全同态加密研究与设计6.5.2 乘法同态性.836.5.3 密钥交换.836.6 层次型全同态加密方案.846.7 密文同态计算的噪音分析.856.7.1 加法噪音分析.856.7.2 乘法噪音分析.856.8 选择具体安全参数.866.8.1 方案的参数属性.876.8.2 具体参数.876.9 总结.88第七章 基于BINARY-LWE噪音控制优化的全同态加密方案改进.907.1 问题的提出.907.2 解决问题的主要思路.907.3 改进的基本加密方案.917.4 方案的同态属性.927.4.1 加法同态性.927.4.2 乘法同态性.937.4.3 密钥交换.937.5 层次型全同态加密方案.947.6 密文同态计算的噪音分析.957.6.1 加法噪音分析.957.6.2 乘法噪音分析.957.7 选择具体安全参数.967.7.1 方案的参数属性.967.7.2 具体参数.977.8 总结.99第八章结论.100参考文献.103致谢.114在学期间的研究成果及发表的学术论文.115VIII南京航空航天大学博士学位论文图表清单图2.1格的几何形状.12图2.2格的基本平行体示例.12表3.1噪音依赖分析与管理噪音的方法.28表3.2 LWE上BGV方案的参数尺寸.29表3.3 环LWE上BGV方案的参数尺寸.32表3.4 LWE上Bral2方案的参数尺寸.33表3.5 环LWE上Bral2方案的参数尺寸.37表3.6 LWE上 GSW13方案的参数尺寸.38表3.7 BGV方案、Bral2方案和GSW13方案的参数尺寸.40表3.8 BGV方案、Bral2方案和GSW13方案的噪音增长公式.41表3.9安全等级80位，高斯参数尸8,敌手优势*=2-1,2-32,2-8，在模4的取值下，的最小值.43表3.10安全等级80位，高斯参数尸8,敌手优势adv=2/，不同电路深度下维数和模的尺寸.44表3.11安全等级80位，敌手优势adv=2，三个方案的公钥、私钥和密文的具体尺寸.45表4.1 BGV方案、Bral2方案和GSW13方案的参数尺寸.59表4.2安全等级80位，高斯参数尸8,敌手优势adv=2L不同电路深度下维数和模的尺寸60表4.3安全等级80位，敌手优势adv=2L三个方案的公钥、私钥和密文的具体尺寸61表5.1本章方案、NTRU方案和GSW13方案的参数尺寸.77表5.2安全等级80位，高斯参数尸8,敌手优势adv=2/，不同电路深度下维数和模的尺寸.78表5.3安全等级80位，敌手优势adv=2/，本章两个方案的公钥、私钥和密文的具体尺寸.79表6.1本章方案的参数尺寸.89表6.2安全等级80位，高斯参数尸8,敌手优势adv=2L不同电路深度下维数和模的尺寸90 表6.3安全等级80位，敌手优势adv=2/，本章方案与LWE上Bral2方案的公钥、私钥和密文 的具体尺寸.88表7.1本章方案的参数尺寸.99表7.2安全等级80位，高斯参数尸8,敌手优势adv=2L不同电路深度下维数和模的尺寸.100 表7.3安全等级80位，敌手优势adv=2，本章方案、LWE上Bral2方案和第6章方案的公钥、私钥和密文的具体尺寸100IX基于格的全同态加密研究与设计注释表长度符号意义符号意义Z整数环Xz上的噪音高斯分布耳模9整数环，中的整数B%分布的界R=Zx/f(x)表示系数是整数的多项 式环。如果小)=/+1,则R中的元素都是次数 小于的多项式。lbA表示将列向量与矩阵力 级联，形成一个新的矩阵L-J向下取整A安全参数向上取整negl(n)negl(n)=o(nc)，又称可 忽略的口取最近的整数A(A)随机格IWLHall1范数，表示向量的长度最大范数，表示向量的IHL2范数，表示向量的长度X南京航空航天大学博士学位论文第一章绪论1.1 全同态加密引言加密已经成为保证数据在公共信道中安全传输的一个基本手段川。密文对于拥有相应密钥 的人来说，可以解密获得明文，而对于没有密钥的普通人来说，密文就显得没有意义了。这不 禁让人们提出一个有趣的问题：是否无需密钥就能够对密文做任意功能的计算呢？从代数角度 看这就是同态性，这个问题已在1978年由Rivest,Adleman和Dertouzos提出后就成为一个开 放问题，当时称为隐私同态加密，也就是现在所说的全同态加密。全同态加密提出后就成为 密码学界的一个开放难题，被誉为密码学界的“圣杯”3o全同态加密是指能够在不知道密钥的情况下，对密文进行任意计算，即对于任意有效的/及明文加，有性质：f(Enc(m)=Enc(/(m)o这种特殊的性质使得全同态加密有广泛的理论 与实际应用，例如：云计算安全、密文检索、安全多方计算等等。以云计算安全为例，用户首 先将数据加密，然后再将密文数据存储在云平台中。但是，当用户向云平台提出计算请求时(例 如查询、统计等操作)，由于云平台不能识别密文数据，而且传统加密算法不支持对密文的任意 同态计算，所以云平台无法对密文进行任意计算。然而，数据加密如果采用全同态加密算法，第三方可以在不知道密钥的情况下，对密文进行任意计算，而且计算结果解密后等于对明文做 同样计算的结果。全同态加密算法的这种同态性质使得我们操作密文就像操作明文一样。因此研究全同态加密有重要的科学意义与应用价值！2009年Gentry构造出第一个全同态 加密方案图，这一杰出的工作是密码学界的一个重大突破，也是计算机科学界的一个突破，解 决了困扰人们30多年的开放难题，同时也拉开了全同态研究的帷幕。历史上相继产生过许多单同态加密方案25-冈，这些方案要么是满足加法同态，要么是满足 乘法同态，还有一些能够同时满足有限次加法与乘法的同态方案15-现。止匕外“Polly Cracker”方案 血尽管能够对密文执行任意电路的计算，但是其密文大小却随着电路的深度呈指数增长，而且 遭受着各种安全性攻击。还有基于电路隐私安全的两方计算方案mi该方案的通信复杂度随着 电路尺寸的增长而增长。上述这些方案没有一个是全同态的，直到2009年Gentry构造出第一 个全同态加密方案。Gentry构造第一个全同态加密方案是基于理想格，由于环上的理想从代数意义上是支持加 法和乘法的，所以用它来构造全同态加密方案是很自然地应用。该方案能够任意对密文做加法 和乘法计算。由于Z2上的加法和乘法在操作上可形成完备集，所以全同态加密方案能够对密文 进行任意多项式时间的计算以。传统的安全计算都是采用电路模型的，其原因是电路模型需要 基于格的全同态加密研究与设计“接触”所有的输入数据，因而不会泄露任何信息，所以Gentry构造的全同态加密方案也是采用 电路计算模型。最近人们设计出基于图灵机模型的全同态加密方案囚-24。Gentry构造方案的出发点是要尽可能的缩小解密电路的复杂度，因为只有这样初始方案才 能够运行其增强型解密电路，最终才能够获得全同态加密。方案所选择的代数结构是理想格，是因为在格里解密操作比较简单，绝大多数都是矩阵向量乘或是内积，它们都属于NC1,具有 低的解密电路复杂度，此外理想格像格一样具有加法结构，同时它还具有乘法结构的特性，可 以说两全其美。在Gentry的构造框架下，由于指数型的加密方案（例如RSA）的解密电路不属 于NC,所以这些方案是无法进行“启动的（Bootstrappable）”。从2009年至今产生了许多全同态加密方案及实现与优化网25-47。第一代全同态加密方案 囚-33都是遵循Gentry复杂的构造方法。本质上这些方案都是在各种环的理想上，首先构建一个 部分（Somewhat）同态加密方案（即方案只能执行低次多项式计算），然后“压缩”解密电路（依赖 稀疏子集和问题的假设），从而执行自己的解密函数进行同态解密，达到控制密文噪音增长的目 的，最终在循环安全的假设下，获得全同态加密方案。尽管同态解密是实现全同态加密的基石，但是同态解密的效率很低，其复杂度为京（下）国。第二代全同态加密方案（31,32,33,34,35,47）构造方法简单，基于LWE（环-LWE）的假设 1148,其安全性可以归约到一般格上的标准困难问题，打破了原有的Gentry构建全同态加密方 案的框架。首先构建一个部分同态加密方案，密文计算后，用密钥交换（key switching）技术 控制密文向量的维数膨胀问题，然后使用模交换技术控制密文计算的噪音（noise）增长。通过 上述方法无需同态解密技术，就可获得层次型全同态加密方案，即方案可以执行多项式级深度 的电路，可以满足绝大多数应用。要想获得“纯”的全同态加密方案，依然要依赖同态解密技术。然而同态解密技术效率低下，而且需要依赖循环安全的假设，实践中不予考虑。2013年Gentry 提出了一个基于近似特征向量的全同态加密方案无需密钥交换技术和模交换技术就可以实 现层次型全同态加密方案。该方案的安全性基于LWE问题，密文的计算就是矩阵的加法与乘 法，是一个非常自然简单的一个全同态加密方案。2009年至今，全同态加密技术发展很快，Gentry等人以环-LWE上的BGV方案为例以,通过各种优化，该方案的渐进复杂度达到V polylog（而Gentry最初方案的渐进复杂度为 d（26）49o在实际运行方面，环-LWE上的BGV方案以AES加密方案做为测试对象，采用密 文打包技术的优化岑,整个AES的十轮操作大约需要36小时，平摊开销下来平均每个AES密 文块的操作大约需要40分钟网，比最初Gentry-Halevi的实现方案助快了约2个数量级。尽管 全同态加密方案的效率不断提高，但是全同态加密的构造方法并没有大的突破，离实际应用依 然有距离，而低效率的根本原因与构造方法直接相关。目前构造方法的发展趋势是自然、简单、直观。在国内全同态加密研究方面，也提出了一些全同态加密方案与应用。据我们所知,胡予濮和 2南京航空航天大学博士学位论文王凤和提出了针对基于主理想格全同态加密方案26的特定攻击方法5叫汤殿华、祝世雄、王 林等提出了一个基于环LWE上的全同态加密算法HU；于志敏，古春生等人提出了基于整数近 似GCD问题新的全同态加密方案；汤殿华等提出了一个较快速的整数上的全同态加密算法53；刘明洁，王安等人对目前全同态加密方案进行了综述分析5引；张爽，杨亚涛，李子臣构造了一 个基于LWE问题的全同态加密体制FHE-CF55o 张永,温涛,郭权和李凤坤通过引入全同态加 密算法提出了一种对偶密钥建立方案5旬；陈嘉勇，王超,张卫明和祝跃飞采用全同态加密算法设 计安全的密文域图像隐写术卬;孙中伟，冯登国和武传坤提出了基于加同态公钥密码算法的匿 名数字指纹方案型；光炎，顾纯祥,祝跃飞等人基于提出了基于LWE构造了无证书全同态加密 方案光炎，顾纯祥,祝跃飞等人基于LWE构造了基于身份的全同态加密体制6叫1.2 全同态加密思想由于不存在一个天然的全同态加密方案，所以目前所有的全同态加密方案都是“构造”出来 的。Gentry构造全同态加密方案的思想可以抽象概述为：首先在环R上构造一个线性纠错码C,“线性”意味着保证加法同态性，“纠错”意味着码字中存在错误，如果该错误在一定范围内就可 以纠错。而且。是环上的一个理想，其基有两种表示，一种是“好”的表示，用来做密钥，可以 对大的错误进行纠错（相当于解密），当错误超过上限后将无法纠错（即无法解密）。另外一种 表示是“坏”的表示，用来做公钥，可以产生随机的码字，用于加密。由于线性纠错码。的线性 特性决定了其具有加法同态特性，另外。是环上的一个理想，所以其乘法也具有同态特性，然 而由于错误存在上限，因此仅对有限次的乘法计算保持其同态特性。该思想形成的方案就是部 分（Somewhat）同态加密方案，由于密文计算中错误增长的原因，该方案只能对密文进行有限 次的运算。最初的方案都可以用这种思想解释。例如多项式环上构造的方案回2叱整数环上的 方案2”矩阵环上的方案口叫由于密文中的错误（也称为噪音）会在密文计算中增长（乘法运算的噪音增长尤其显著）,导致密文计算是有界的，超过这个界后密文解密就可能失败。因此控制密文噪音就成为实现全 同态加密的一个关键问题。Gentry解决这一问题使用了一个重要技术：同态解密。即对密文及 相应的密钥按位分别加密后输入解密电路，在Evaluate算法中同态执行解密电路将输出一个新 的密文（称为密文更新），该密文解密后还是原来的明文。如果新密文的噪音还允许进行一次乘 法运算，那么在每次密文计算后，通过同态解密更新密文就可以进行下一次计算，递归上述过 程就可以对密文进行无限次的计算，从而实现了全同态加密。然而成也萧何，败也萧何,同态解 密的计算量是非常大的，是导致全同态加密方案效率低下的一个根本原因。所以如何改进与提 高或者寻找到一种更有效的替代同态解密的技术是一个值得研究的开放问题。使用同态解密技术有个前提条件：解密电路的深度要小于部分同态加密方案所能计算的深 3基于格的全同态加密研究与设计度，即Evaluate算法要能够执行解密电路。如果该条件成立，就称部分同态加密方案获得了启 动（Bootstrapple）。然而在最初的一些方案中，解密电路的深度都是大于部分同态加密方案所 能计算的深度，因此需要使用“稀疏子集和问题”的假设来压缩解密电路，以达到降低解密电路 深度的目的，从而获得方案的启动。如果再假设循环安全的（即假设用方案自身的公钥加密自 身的密钥作为公钥是安全的），即可获得“纯”的全同态加密方案（即可以进行任意深度电路的计 算）。上述构造思想中的环结构保证了乘法计算，但是对于LWE（环LWE）上的加密方案由于 没有环结构，所以无法提供密文向量的乘法，一度成为LWE（环LWE）上构造全同态加密的 最大障碍。Brakerski在参考文献31中引入了再线性化技术与维数模约减技术，成功的解决了 在没有环结构的方案中进行密文乘积的问题。后来在BGV方案中经过改进形成了密钥交换技 术和模交换技术。在基于LWE（环LWE）的全同态加密方案中，密文乘积定义为两个密文ci 和功的张量。1区。2，对应的密钥为SBs。按照这种形式的乘法定义，一方面，密文乘积将导致 密文维数的膨胀，只能进行常数次的密文乘法计算；另一方面，同样面临着噪音在乘法中迅速 增长的问题。解决这些问题，一方面通过使用密钥交换技术，可以将密文的维数还原到原来的 维数，因此可以进行下一次密文的乘积；另一方面使用模交换技术，可以将增长的噪音约减回 原来的噪音大小上。因此，不需要启动就可以获得层次型全同态加密方案（可以执行任意多项式 深度的电路），所以不再需要稀疏子集和问题假设和循环安全假设，这是全同态加密思想上的一 次飞跃，打破了原有的Gentry构造框架，效率上也得到了极大地提升。目前环-LWE上的BGV 方案使用的就是这种构造方法，其每个门电路计算复杂度为。（八万）（这是没有优化的情况下），其中是电路的深度。比最初的方案（6（下）有了极大地提升！2012年Brakerski在美密会上 提出了 Bral2方案目,该方案只需使用密钥交换而无需使用模交换技术就能够获得全同态加密 方案，使得全同态加密方案的构造变得简单。然而密钥交换技术又是当前框架下的瓶颈，因为使用密钥交换技术需要在公钥里添加许多 用于密钥交换的矩阵，增大了公钥尺寸。计算上，每次密钥交换时密文都需要乘以一个高维矩 阵，例如基于LWE的方案其密钥交换矩阵一个（+1）2logqx 5+1）的矩阵，这直接影响了方 案的效率。所以如果能够去除密钥交换技术或改进提高都能够再次提升全同态加密的效率。2013 年Gentry提出了一个基于近似特征向量的全同态加密方案（GSW13方案）35,由于密文使用 的是矩阵，所以密文的乘积不存在密文向量的膨胀问题，因此无需密钥交换技术和模交换技术 就可以实现层次型全同态加密方案。该方案的安全性是基于LW