英语原文共 10 页
基于理想格的全同态加密方案
Craig Gentry
摘要
我们提出了一个全同态加密方案——即，一个可以允许我们在无需解密的情况下，在加密数据的基础上对电路进行计算。我们的解决方案分为三个步骤。首先、我们提供一个一般的结果——构建一个可以求任意电路的值的加密方案，这个结果能够构建一个可以求它对应（有一些轻微的扩展变形）的解密方案的值；我们称这样的一个可以求出自己（扩展的）解密电路的方案为“自举的”。
接下来，我们将描述一个基于几乎“自举的”理想格的公钥加密方案。基于格的典型的加密系统的解密程序具有低的电路复杂性，通常受NC1中的内积计算的影响。而且，理想格同时满足加法和乘法同态（一个格的多项式环模公钥的理想），适合一般的计算电路。
并不幸运的是，我们初始的方案并不是非常满足自举性——在格的维度中，这个方案被正确计算时的深度可以达到指数级的，就像解密电路的深度，但是后者的深度比前者要大的多。在最后一步中，我们将展示怎么去调整这个方案以降低这个解密电路的深度，所以存在一个没有降低深度的自举的加密方案可以进行计算。抽象地说，我们是通过让加密器去执行解密进程，减少解密器的工作，来达到这个目的的，很像是在服务器辅助密码系统中，服务器为解密器留下的工作较少。
类别和主题：E.3[数据加密]：公钥加密系统
关键字：算法，设计，安全性，理论
1、引言
我们提出了关于“构建一个全同态加密方案”这一开放性问题的一个解决方案。这个想法最初被叫做隐秘同态，在Rivest, Adleman and Shamir三人提出RSA公钥加密方案后的很短的一段时间内被Rivest, Adleman and Dertouzos三人提出。最基础的RSA是一个满足乘法同态的加密方案——即，给定RSA的公钥和密文，我们可以很容易的计算出由原始明文的产物计算的密文：。Rivest和其他人最后问了一个很自然的问题：我们可以用这样一个全同态加密方案做什么：一个带有高效算法的方案，对于任意有效的公钥；任意电路（不仅仅是包含乘法同态的的电路）；和任意密文；输出；一个基于的关于的有效加密？他们的答案是：我们可以在对加密数据进行任意的计算——即，我们可以在不使用解密密钥的情况下处理加密数据（查询，写入，对它进行任意操作，只要能够被高效的表达为一个电路）。作为一个应用示例，他们假定一个个人数据库：使用者在一个不被信任的服务器上，以加密的形式储存他的数据，也即允许这个服务器去处理和反应，用户的查询操作（该操作比一些方案里的更加简明：服务器仅仅将所有的加密数据传回给使用者去进行操作）。从那以后，针对全同态加密，密码学家迅速产生了一系列的“超级”的应用。但是，在我们这个方案提出之前，我们还没有一个切实可行的构建方案。
1.1 同态加密
一个同态公钥加密方案包含有四个函数：，，和以和附加的函数，这个函数的参数包括公钥，一个允许电路的集合中的电路和一个密文列表，输出为一个密文。所有这些函数的计算复杂度是关于安全参数和（在的情况下）的的大小的多项式。如果对于任意输出的密钥对，任意电路，任意的明文和任意的密文，其中，有下面的结果：
则方案对于中的所有电路都是正确的。
单独地，针对一些不重要的方案正确性也能够满足正确性。所以，我们需要一个独立于（或者一个依赖于的深度，而不是的大小）的参数，及关于的函数来确定来界定密文的尺寸以及解密的时间。
定义1 （同态加密）针对中的电路，方案是同态的，如果方案对于是正确的，而且可以表达成一个大小为的电路。
定义2 （全同态加密）方案是全同态的，如果它对于所有电路都是同态的。
定义3 （同级全同态加密）一个加密方案集合 是同级全同态加密的，如果它们均使用同一个解密电路，对所有深度不大于的电路，是同态的，而且的计算复杂度是关于，和的大小（就而言）三个参数的多项式。
注1 为满足双方计算设置，有人可能需要一些另外的性质：和有相同的输出分布，或者有一些随机的程序能够产生同样的输出分布。我们将在第7节讨论这样的隐秘电路。
现在，我们将注意力放在构建一个语义安全的加密方案能够抵抗选择明文攻击（或者仅仅是“语义安全的”）。不幸的是，一个具有有效同态性质的加密方案针对适应性的选择密文攻击（CCA2）不具有语义上的安全性，因为它是可塑的。在文献[3，16，52]中有关于CCA2的简单概念，但是他们没有应用于全同态加密。然而，构建一个满足CCA1安全的全同态加密方案是一个很有趣的开放性的问题。
1.2 我们的结果
我们利用理想格构建了一个全同态加密方案。我们的结果可以粗略的分为三个部分：一个一般的“自举的”结果，一个使用理想格的“初始构建”和一个为能够满足自举性的“压缩解密电路”的技术。
我们的研究开始于第二步：第3节中描述的一个应用理想格，而且对于低深度电路满足同态的PKE方案。其中，密文的形式为v x，其中v是理想格中的一个向量，x是一个编码明文后的“误差”或“位移”向量。我们将密文向量用多项式环中的元素的参数向量来表示，利用环的加法和乘法对密文进行操作，即或者，同时导出下一层明文的加法和乘法规则。就这个方案来说，它在先前的工作上有了提高。它较于Boneh-Goh-Nissim方案是有利的[11]；对更深的加密深度的电路是同态的，而且对于加法操作基本上是允许无限次的。方案的安全性是基于环上理想格的最短向量问题的一个变式。
仅对于低深度的电路是同态的，因为“误差”向量的长度会随着加法和（特别是）乘法操作而增大；最后它会变得太长以致于无法正确解密。那我们自然会问：我们可不可以“刷新”那些误差向量很长的密文去获得一个带有较短误差向量的新的密文？显然，如果刷新之后我们可以完全解密密文，那就可以刷新！这就是在bootstrapping技术背后的想法：我们的确解密了密文，而且是同态的！
特别地，假设加密方案是自举的，其明文空间为，加密电路是布尔类型的。假设我们有一个需要刷新的密文，这个密文由明文利用公钥加密得到。这样我们就可以对它进行同态解密了，如果我们同时还有对应的私钥，并由第二个公钥加密得到：记的长度为加密密钥长度。考虑下面的算法程序。
设置
输出
由上面的程序看出，的输入为的一部分和，它们具有加密得到。接下来，方案被用来同态地计算解密电路。输出的是基于 中加密得到的加密结果。利用解密电路，我们消除了第一个密文的误差向量，但是同时引入了一个新的误差向量。但从直观上来看，我们尽可能的将第二个误差向量的长度变短了。
假设不仅包括，而且包括由NAND（一个NAND门连接两个复制的）的扩展的。然后我们说是自举的。
定理1 （非正式的）我们可以从任意（语义安全的）自举的加密方案构建出一个（语义安全的）同级全同态加密方案的集合。
方案的公钥包含了个方案的公钥，每个公钥对应了每一层电路和一系列非周期的被加密的私钥。按照下面的方式对d深度的NAND电路进行计算：方案中，利用加密的密文均关联着第层电路的两条路，然后执行函数使得它们变成由加密得到，同时在这一层电路应用NAND门，并且令。如果方案安全地加密了依赖密钥的信息（这是KDM安全的）[9,24,12]——即，粗略地讲，如果提供一个加密关于密钥函数的密文没有损害安全性——那么的公钥需要不被公开；我们对私钥可以有一个“循环”，甚至一个“秘密的循环”，而且这个导出的方案是全同态的。在第2节中有更多准确的细节。
在第4节中，我们描述了一个对方案的“调整”方案，分析了它的解密电路的复杂度，并且解释了为什么我们不能证明它是自举的。在第5节中，我们叙述了一个方案的变型，用表示，方案包含了一系列向量组成的私密的稀疏子集（它的和与的私钥相关）。这就是我们可以用一个稀疏子集的和来重新表示解密方案，代替了需要电路满足低深度和自举条件的全矩阵向量形式。它还需要一个附加的假设：简略的讲就是，已知一个集合稀疏子集的和求出这个集合来时困难的。在服务器辅助系统解密中同样的假设也被应用于分析。
定理2 （非正式的）方案式自举的，并且具有语义上的安全（在两个假设条件下）。
1.3 其他相关的工作
对于不具有语义安全的同态加密方案，像基本的RSA，可能会有更强的攻击来攻击他们的单向性。Boneh和Lipton[13]已经证明了任意的基于环上的代数隐秘同态方案可以在一个数论假设的条件下，利用低于指数级的时间破解，如果这个方案是确定的或者提供了一个平等测试准则。具体可以看文献[35]和[18]。
Goldwasser和Micali[23]提出了首个具有语义安全的同态加密方案（而且引入了语义安全的定义）。他们的方案是构建在上，满足加法同态的；用我们的术语来讲，他们方案的允许电路集合中的电路都可以进行XOR操作。其他的被证明具有语义安全性的满足加法同态的加密方案包括Benaloh[8], Naccache-Stern[42], Okamoto-Uchiyama[46], Paillier[47]和Damgard-Jurik [19]。还有一些其他使用格或者线性编码的满足加法同态的加密方案可见[22,50,27,36,37,4]。[20]中的EIGamal方案满足乘法同态。
既具有语义安全又同时满足加法和乘法同态的加密方案包括Boneh-Goh-Nissim [11]（二次公式）和Fellows and Koblitz提出的“Polly Cracker” 方案[21,29,30,31]（满足任意电路，但密文尺寸呈指数级增长）。Sanders,Young 和Yung[56,7]（SYY）利用隐秘电路加法同态方案构建了一个可以处理NC1电路的隐秘电路方案。Ishai and Paskin [26]利用线路图完成了这项工作，不仅覆盖了NC1所有的电路（Barrington[6]），而且他们方案中的密文长度更短——和线路图的长度成比例的而不是它的大小，尽管计算时是和它的大小成比例的。
2. 自举加密
为了满足自举性，方案需要不仅能够求它的解密电路的值（该解密电路仅允许对相同的明文进行解密），而且对它的扩展电路，这样我们就可以通过一个电路对明文执行有效的操作和进程。
定义4 （扩展解密电路）在包含单位门的明文空间中，令为带有输入输出的一系列门的集合。对于，-扩展解密电路由连接多个的复制的-门组成（复制的数量等于输入的数量），其中的输入为一个私钥和密文，他们的格式与中的元素相同。我们由定义-解密电路的集合，。
定义5 （自举加密）令为同态加密方案的电路集合。我们说是关于自举的，如果
针对导出的方案集合我们也可以很快的定义，并且有一下几条定理。
定理3 令是关于门集合自举的，那么集合是同级全同态加密的（针对由中的门组成的电路）。
定理4 令具有优势的算法程序可以破坏的语义安全，那么必定有一个算法程序可以以至少的可能性破坏的语义安全，其中是定义4中的，是的时间多项式。
注意定理3中的是任意的。例如，对于中的每个门均可以是具有（与门、非门、或门）的电路，电路深度为，输入端数为2；由于的这个性质，定理3可以使方案正确地对深度为的“正规”电路进行计算。
现在，我们来具体的说明同级全同态加密方案。令是关于门集合自举的，对于任意的整数，我们利用构建一个方案 ，可以处理所有由中的门组成的深度为的电路。当我们提到电路中线路的层数，它的意思是输入线路中门的层数。我们下面用表示由扩展的电路集合，其中的电路由中的门组成，深度为（的复制作为深度为的电路的输入）。
，输入参数为一个安全参数和一个正整数。因为，像定义4中的一样，令
其中，是关于中元素的表示，这个函数的输出为密钥和公钥 ，因为，令为这样的一个方案：使用密钥和公钥。
，输入参数为一个公钥和一个明文，输出为一个密文。
，输入参数为一个私钥和一个密文（利用加密得到），输出为。
，输入参数为一个公钥，一个由 中门组成的深度最大为的电路和一个输入密文的列表（其中每个输入密文是由加密得到）。我们假定中的每条线路连接连续层级的门；如果不能的话，则增加单位门以满足假设。如果，函数输出并终止，否则则执行下面的步骤：
令
令
执行
，输入参数为一个公钥，一个由 中门组成的深度最大为的电路，和一个输入密文的列表（其中每个输入密文是由加密得到）。它利用来扩展；得到的结果记为。为一个输入密文的列表，每个输入密文是由代替得到，其中，，是用中元素表示得到。函数最后输出。
，输入参数为一个公钥，一个由输入密文组成的列表（每个输入密文应该是的一个输出）和一个电路。设定为的子集，由开始的层电路组成，由的输入密文导出，其中，在第层电路关联线路的密文设置为，这里，是带有输出线路的的子集，是作为的输入密文。最终函数输出为。
关于的计算复杂度：
定理5 对于一个深度最大为和大小为（线路的数量），在电路中执行函数的计算复杂度相当于在的电路中最多应用次函数和次函数，其中为定义4中的。
像上面提到的，如何方案是KDM安全的，我们就可以使公钥缩短到包含，并在下加密，形成一个一个“自循环”而不是一个加密密钥的非循环链。这个方案是全同态的，具有KDM安全性，正确性则依赖以上方案的正确性。
3. 一个初始的构建
我们现在的目标是构建一个就普通的门集合来讲是自举的加密方案，例如，包含NAND门和平凡门。在这一章节我们描述了一个初始的尝试。在第4节中，我们将叙述一个对这个初始构建做了一些调整后的方案，并发现它的解密复杂度仍然很大，无法满足自举性。我们最终在第5节实现了这个自举方案。
3.1 简要地，初始的构建
我们开始的尝试是建立在环和理想上的；
资料编号：[3903]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
