陈智罡-全同态加密释疑.docx

全同态加密释疑（一）：四个算法（1）陈智罡2009年全同态加密（Fully Homomorphic Encryption）的诞生，不仅是密码学界的一个大的突破（Breakthrough）,而且是计算机理论界的一个突破。自从2011年创建了全同态加密QQ群，从几十号人到现在的将近200人，来自各个大学，包括国外。可见人们对全同态加密研究的热情。另外在网上有许多同学问我一些问题，有些问题很雷同，可能也是初学者必经之路。全同态加密的入门确实比较难。作为一个过来者，非常愿意分享我的一些心得，所以这里我会把一些共性的问题，用一种深入浅出的方法讲述，希望每个人都能看懂。其实在全同态加密论文的背后，有许多可以说出来的秘密，只不过这个秘密在论文里没空间也不适合讲，那么这里就搞一个专题“全同态加密释疑”，细说从头每个让你困惑的秘密。如果有愿意加入的朋友，可以一起分享心得体会。今天说说全同态加密的四个算法。可能有些人会说，这个谁不知道，但是知道并不意味着清楚，只有深刻理解了这四个算法的含义，尤其是第四个算法的含义，才能清楚什么是部分同态加密方案，什么是执行自己的解密电路等等概念。通常一个公钥加密方案有三个算法：KeyGen算法（密钥生成），Enc算法（加密），Dec算法（解密）。但是在全同态加密中，除了上述三个算法之外，还包含第四个算法：Evaluate算法（密文计算），这个算法的功能是对输入的密文进行计算。首先说说KeyGen算法（密钥生成）。该算法用于生成公钥和密钥，公钥用于加密，私钥用于解密，这个地球人都知道。但是还可能生成另外一种公钥，即密文计算公钥，我们把它称之为Evk。密文计算公钥Evk的作用是在执行Evaluate算法时用到，而且Evk的形式与使用的全同态方案直接相关。例如，如果是通过启动技术（Bootstrapple）获得全同态加密，即每次密文计算前要用同态解密约减密文的噪音，这时Evk就是对密钥的每一位加密后生成的密文，即密钥有多少位，Evk里包含的公钥就有多少个。Evk中每个公钥的大小就是使用Enc加密后产生密文的大小。典型的代表就是Gentry的理想格方案以及后续的整数上的方案。当然还有其他情况，例如，如果使用密钥交换与模交换技术获得全同态加密，典型代表就是BGV方案。这时Evk中包含的就是L1个矩阵，L是方案中电路的深度，该矩阵用于密钥转换。每次密文计算后，都需要使用Evk中的公钥将维数扩张的密文向量转换成正常维数的密文向量。当然还有一种情况就是不需要Evk，例如在Crypto13会议的论文GSW13中，Gentry使用的密文是矩阵（方阵），所以密文乘积或相加不会产生密文维数改变的事情，所以在密文计算时没有用到公钥，这也是该论文可以产生基于身份或基于属性全同态加密方案的根本原因。关于Evk就说了这么多，你觉得简单么？一个成功男人的背后，有多少，那么一个概念的背后就有多少个概念在支撑。千万别小看了概念，只有善于抓概念，才能体会方案的脉络。继续说全同态加密中的其他三个算法。Enc算法（加密）和我们平常意义的加密是一样的，但是在全同态加密的语境里，使用Enc算法加密的密文，一般称之为新鲜密文，即该密文是一个初始密文，没有和其他密文计算过。所以新鲜密文的噪音称之为初始噪音。这个相当重要。Dec算法（解密）也和我们平常理解的一样，就是对密文的解密，但是这里解密算法不仅能对初始密文解密，还能够对计算后的密文解密。但是由于部分同态加密方案中密文存在噪音，例如在整数上的全同态加密方案里，密文乘积的噪音是噪音之积，密文加法的噪音是噪音之和。所以当密文计算到一定程度，其噪音将超过上限，所以对这样的密文解密将可能失败。全同态加密的关键就是对噪音的控制，使之能对任何密文解密。最后一个算法：Evaluate算法（密文计算），这个算法是整个全同态加密四个算法中的核心。可以做个这样的比喻：前面三个算法是大楼的地基，后面这个Evaluate算法就是大楼。这个比喻在后面会体会到它的用意。密文的计算是在电路里进行的，电路是分层的，电路深度越深，层数越多，密文就能够进行更多次的计算。随便提一句，密文计算的次数等于电路深度的对数。什么是计算次数？例如c1*c2，就是进行了一次计算，次数为2，c1*c2*c3就是进行了两次计算，次数为3。在全同态加密中，我们一般用乘法次数来衡量计算次数，这是因为乘法的噪音比加法噪音增长的快很多。Evaluate算法有三个输入，第一个输入是计算公钥Evk，就是我们在上次博文里讲到的。Evk可以没有。第二个输入是函数f，就是Evaluate算法所要执行的函数，可以是任意函数，因为全同态加密的目标就是对密文能够进行任意计算。当然这个函数也可以是“解密函数”，Gentry通过观察发现了一个秘密，等会我们说。第三个输入是密文，理论上可以有无穷多个密文，但是这是不可能的。所以Evaluate算法就是将密文输入到函数f里进行计算。我们知道在全同态加密的方案里，密文都是含有噪音的，密文的计算会导致噪音的增长，如果把函数f表示成电路，那么Evaluate算法实际上只能够对有限深度L的电路进行计算，超过这个深度L的电路就不行了。所以我们把这样的方案称之为部分同态加密方案。由此可见Evaluate算法的重要性，全同态加密就靠它了。还记得刚才的比喻么？Evaluate算法相当于大楼，这个大楼的层数是有限的，而全同态加密的目标是无限高！所以噪音问题导致了Evaluate算法不能够对任意电路（函数）进行计算。而全同态加密追求的就是Evaluate算法能够对任意电路进行计算，怎么办？那只有控制噪音问题了。如何控制噪音呢？下回分解。全同态加密释疑（二）：一个技术陈智罡在全同态加密（Fully Homomorphic Encryption）方案中，有一个非常重要技术：同态解密。为什么要同态解密，前面说过噪音问题是实现全同态加密方案的最大障碍。Gentry在实现全同态加密方案时，注意到可以在Evaluate算法中执行自己的解密函数，那么输入的数据是什么呢？解密函数当然输入的是密钥sk和密文c。但是不要忘了Evaluate算法是如何定义的。Evaluate算法是对输入的密文c1,c2,执行函数f的操作，也就是对密文进行计算，其实隐含在其中的本质是对密文做同态计算，即计算后的密文解密后要等于对明文做同样的计算，如果这点做不到，那么Evaluate算法即使能对密文做很多次运算，也是没有意义的，这点一定要清楚。这就是两种形态，明文态和密文态，两种形态对应的是同一个计算电路。在明文态，输入电路的是明文，而这些明文都是位（因为是布尔电路）。在密文态，输入电路的就是把每一个明文变成密文就可以了（算术电路）。这是我的独家比喻，版权所有。而现在如果f是解密函数，那么输入的密文是什么呢？只要看看明文态的时候输入的什么就知道了。在明文态，对于解密电路，输入的肯定是密钥sk的每一位二进制位，以及密文c的每一位二进制位，因为是布尔电路，所以输入的数据都要化成二进制位的形式。好了，现在在密文态，相应的把明文位变成密文就可以了，原来是一个位的地方现在变成了一个密文，那么将这些密文输入到解密电路中，结果是什么呢？是一个密文，这个密文解密后等于在明文态对明文做同样计算的结果。现在我们关心的是这个从解密电路里出来的新密文和原来的密文c之间有什么关系？这两个密文对应的是同样的明文。而我们关心的是两个密文的噪音一样么？肯定是不一样的，因为密文计算的噪音会随着计算次数不断增长。而从解密电路里出来的密文的噪音是一个固定值，是保持不变的。惊讶吧？我们希望的是什么？是解密电路里出来的密文的噪音比原密文的噪音小么？NO！我们要求没有这么高。我们只要求解密电路里出来的密文的噪音，还允许再进行一次乘法计算就可以了。为什么？因为如果上面的要求成立的话，那么每次密文计算前，只要通过同态解密，出来的密文就可以保证再进行一次计算，不断循环下去，就可以做无限次计算了。当然要想做无限次计算还需要一个假设条件就是：循环安全。如果不做这个假设，我们只能做深度为L的电路计算。总之能够保证对密文做我们想要的计算了。所以同态解密这个技术，是实现全同态加密的一个关键技术，Gentry就通过它实现了全同态加密。要想使用同态解密，必须在Evaluate算法中能够执行自己的解密函数才可以。很多人都纳闷，解密函数不就是计算一下么，例如在整数方案里解密函数就是：(c mod p) mod2，在LWE或环-LWE上解密函数是：( modq) mod 2，难道不能够执行这些函数？事情往往没有想象的那么简单，且听下回分解。全同态加密释疑（三）：为什么不能运行自己的解密电路陈智罡前面说过，要想降低密文计算带来的噪音，可以通过同态解密的方式得到一个新的密文，这个新密文的噪音是恒定的，所以使得我们可以进行下一次计算，每次计算后都通过同态解密约减噪音，就能够获得全同态加密了。然而同态解密是需要Evaluate算法能够运行自己的解密函数的，在早期的全同态加密方案中（Gentry09，DGHV），包括BV11方案如果最后一步不使用模维数约减的话，Evaluate都不能够运行自己的解密函数。很多同学学到这里的时候，都很纳闷，解密函数不就是一些加法乘法模运算么，为什么计算不了，难道还有计算不了的函数？这个问题是问我的人最多的，今天给大家好好解释一下。所谓的运行不了自己的解密函数，是有语境的，准确的说是“Evaluate算法不能够运行自己的解密函数”，而Evaluate算法的输入是什么？同态解密时，Evaluate算法输入的是解密电路，还有往解密电路里输入的一些密文，这些密文是由密钥和密文的每一位加密而成的，上次博文详细说过这事。那么Evaluate算法做的工作是什么呢？Evaluate算法做的工作就是让这些密文在解密电路里计算，是密文的计算，记住了！由于密文计算过程会产生噪音，所以密文只能够进行有限次的计算，超过这个界就会产生解密的错误。所以如果解密电路的深度小于方案所允许计算的深度（这里方案所允许计算的深度指的是Somewhat同态方案的计算能力），那么就可以完成同态解密的工作。但是如果解密电路的深度大于方案所允许计算的深度，那么就悲催了，我们就不能够使用同态解密这个方法去降低密文的噪音。怎么办？Gentry在他的论文里发明了一种方法叫“压缩解密电路”，就是把解密电路的深度降低，从而满足“解密电路的深度小于方案所允许计算的深度”，这样就可以使用同态解密技术了，方案就可以启动了！压缩解密电路是要付出代价的，同时需要一个假设“稀疏子集和问题”，该问题没有被很好的研究过，所以是假设。不过目前的方案已经不需要压缩解密电路了，例如BGV方案，Bra12方案，这些方案都能够运行自己的解密电路，所以不需要压缩的方法了。同态解密的技术成就了全同态加密的诞生，然而其效率却非常低，所以后面诞生了模交换技术。至于什么是模交换技术，下回分解。全同态加密释疑（四）：转折点：LWE上全同态加密的诞生陈智罡Gentry构造全同态加密方案的思想是非常“规则”的，是按照数学的思维来考虑问题的，就是围绕理想这一概念，因为只有这样才能产生密文的加法和乘法算。Gentry第一个全同态加密方案是基于理想格构造的。方案所选择的代数结构是理想格，是因为在格里解密操作比较简单，绝大多数都是矩阵向量乘或是内积，它们都属于NC1，具有低的解密电路复杂度，此外理想格像格一样具有加法结构，同时它还具有乘法结构的特性，可以说两全其美。所有后面沿着Gentry的构造思路都是按照这个思想来的。直到LWE上的全同态加密方案的出现。Gentry构造全同态加密方案的思想可以抽象概述为：首先在环R上构造一个线性纠错码C，“线性”意味着保证加法同态性，“纠错”意味着码字中存在错误，如果该错误在一定范围内就可以纠错。而且C是环上的一个理想，其基有两种表示，一种是“好”的表示，用来做密钥，可以对大的错误进行纠错（相当于解密），当错误超过上限后将无法纠错（即无法解密）。另外一种表示是“坏”的表示，用来做公钥，可以产生随机的码字，用于加密。由于线性纠错码C的线性特性决定了其具有加法同态特性，另外C是环上的一个理想，所以其乘法也具有同态特性，然而由于错误存在上限，因此仅对有限次的乘法计算保持其同态特性。该思想形成的方案就是部分（Somewhat）同态加密方案，由于密文计算中错误增长的原因，该方案只能对密文进行有限次的运算。最初的方案都可以用这种思想解释。上述构造思想中的环结构保证了乘法计算，但是对于LWE（环LWE）上的加密方案由于没有环结构，所以无法提供密文向量的乘法，一度成为LWE（环LWE）上构造全同态加密的最大障碍。Brakerski在论文Bv11中引入了再线性化技术与维数模约减技术，成功的解决了在没有环结构的方案中进行密文乘积的问题。后来在BGV方案中经过改进形成了密钥交换技术和模交换技术。在基于LWE（环LWE）的全同态加密方案中，密文乘积定义为两个密文c1和c2的张量c1c2，对应的密钥为ss。按照这种形式的乘法定义，一方面，密文乘积将导致密文维数的膨胀，只能进行常数次的密文乘法计算；另一方面，同样面临着噪音在乘法中急剧增长的问题。解决这些问题，一方面通过使用密钥交换技术，可以将密文的维数还原到原来的维数，因此可以进行下一次密文的乘积；另一方面使用模交换技术，可以将增长的噪音约减回原来的噪音大小上。因此，不需要启动就可以获得层次型全同态加密方案(可以执行任意多项式深度的电路)，所以不再需要稀疏子集和问题假设和循环安全假设，这是全同态加密思想上的一次飞跃，打破了原有的Gentry构造框架，效率上也得到了极大地提升。目前效率最高的环-LWE上的BGV方案使用的就是这种构造方法同态加密中经常用到准多项式时间、对数多项式时间、亚指数时间等等。下面这张表详细列出了这些概念的意义及范例。表中poly(x) =xO(1),表示关于x的一个多项式。NameComplexity classRunning time (T(n)Examples of running timesExample algorithmsconstant timeO(1)10Determining if an integer (represented in binary) is even or oddinverse AckermanntimeO(n)Amortized timeper operation using adisjoint setiterated logarithmictimeO(log*n)Distributed coloring of cycleslog-logarithmicO(log logn)Amortized time per operation using a boundedpriority queue2logarithmic timeDLOGTIMEO(logn)logn, log(n2)Binary searchpolylogarithmic timepoly(logn)(logn)2fractional powerO(nc) where 0 c 0O(2lognlog logn)Assuming complexity theoretic conjectures,BPPis contained in SUBEXP.3sub-exponential time(second definition)2o(n)2n1/3Best-known algorithm forinteger factorizationandgraph isomorphismexponential timeE2O(n)1.1n, 10nSolving thetraveling salesman problemusingdynamic programmingfactorial timeO(n!)n!Solving the traveling salesman problem viabrute-force searchexponential timeEXPTIME2poly(n)2n, 2n2double exponential time2-EXPTIME22poly(n)22nDeciding the truth of a given statement inPresburger arithmetic全同态加密释疑（五）：为什么是电路观点陈智罡这个问题是许多刚接触全同态加密研究者困惑的一个问题。也许初学者以为密码学都是基于数论观点的，其实真正的密码学的灵魂落脚点是计算复杂度。密码学中的所有方案必须要依赖于一个数学难题，这是其安全性所在的根本。问题有多难？拿什么来衡量？答曰：计算复杂度。所以有一本很有名但是很枯涩难懂的一本著名密码学理论书：Foundations of Cryptography（Oded Goldreich著），里面深刻阐述了这一观点。但是电路观点在密码学中的方案由来已久。例如，姚期智的论文“How to generate and exchange secrets”就是通过布尔电路观点构造安全函数计算，产生了著名的概念“garbled circuit”。强调一下，电路观点是一种计算复杂度的计算模型，用途是衡量解决问题所需要的资源，例如时间、存储量等。在电路计算模型下