长期以来，完全同态加密一直被认为是密码学的圣杯之一。完全同态加密(FHE)的承诺是强大的：它是一种加密类型，允许第三方对加密的数据执行计算，并获得加密的结果，他们可以将该加密结果交还给拥有原始数据的解密密钥的任何人，而不需要第三方能够自己解密数据或结果。
举个简单的例子，假设您有一组电子邮件，并且您想要使用第三方垃圾邮件过滤器来检查它们是否是垃圾邮件。垃圾邮件过滤器希望其算法具有私密性：要么垃圾邮件过滤器提供商希望关闭其源代码，要么垃圾邮件过滤器依赖于他们不想公开的非常大的数据库，因为这会使攻击变得更容易，或者两者兼而有之。但是，您关心的是数据的隐私，并且不想将未加密的电子邮件上传给第三方。所以这里是你如何做到这一点的：
完全同态加密有很多应用，包括在区块链领域。一个关键示例是可用于实现隐私保护的轻客户端(轻客户端向服务器提供加密索引i，服务器计算并返回data[0]*(i=0)+data[1]*(i=1)+...+data[n]*(i=n)，其中data[i]是块或状态中的第i条数据及其Merkle分支，并且(i=k)是如果i=k则返回1的表达式；轻客户端获得其需要的数据，并且服务器对轻客户端要求的内容一无所知)。
更高效的隐形寻址协议，以及更普遍的隐私保护协议的可扩展性解决方案，这些协议现在需要每个用户亲自扫描整个区块链以查找传入交易。
保护隐私的数据共享市场，允许用户对其数据执行某些特定计算，同时保持对其数据的完全控制。
更强大的加密原语中的一个组成部分，例如更有效的多方计算协议，也许最终还会进行模糊处理。
事实证明，从概念上讲，完全同态加密并不那么难理解！
首先，关于定义的说明。同态加密有不同的种类，有些比另一些更强大，它们通过人们可以对加密数据进行计算的函数来分隔。
部分同态加密只允许对加密数据进行非常有限的操作集评估：或者只计算加法(因此，给定ENCRYPT(A)和ENCRYPT(B)，您可以计算ENCRYPT(a+b))，或者只计算乘法(给定ENCRYPT(A)和ENCRYPT(B)，您可以计算ENCRYPT(a*b))。
某种程度上的同态加密允许计算加法以及有限数量的乘法(或者，多项式直到有限的程度)。也就是说，如果您得到ENCRYPT(X1)...。ENCRYPT(Xn)(假设这些是原始加密，并且还不是同态计算的结果)，您可以计算ENCRYPT(p(x1...。Xn))，只要p(x1…。Xn)是对某一特定度界D具有<；D次的多项式(D通常很低，认为是5-15)。
完全同态加密允许无限的加法和乘法。加法和乘法允许您复制任何二进制电路门(AND(x，y)=x*y，OR(x，y)=x+y-x*y，XOR(x，y)=x+y-2*x*y或只复制x+y，如果您只关心偶数和奇数，而不是(X)=1-x...)，因此这足以对加密数据进行任意计算。
部分同态加密相当容易；RSA具有乘法同态：\(enc(X)=x^e\)，\(enc(Y)=y^e\)，so\(enc(X)*enc(Y)=(Xy)^e=enc(Xy)\)。椭圆曲线可以通过加法提供类似的性质。事实证明，同时允许加法和乘法要困难得多。
这里，我们将介绍一种有点同态的加密算法(即，支持有限数量乘法的人)，这非常简单。克雷格·金特里(Craig Gentry)在2009年使用了这类技术的一个更复杂的版本来创建有史以来第一个完全同态方案。最近的努力已经转向使用基于向量和矩阵的不同方案，但我们仍将首先介绍这项技术。
我们将所有这些加密方案描述为密钥方案；也就是说，使用相同的密钥进行加密和解密。任何私钥HE方案都可以很容易地转变为公钥方案：公钥通常只是一组多个0的加密，以及1的加密(可能还有更多的2的幂)。要加密值，请将非零加密的适当子集加在一起来生成它，然后将零加密的随机子集添加到密文的随机化中，并使其无法辨别其所代表的内容。
这里的密钥是一个大素数\(p\)(可以认为\(p\)有数百甚至数千位数字)。该方案只能加密0或1，并且"；加法"；变成XOR，即。1+1=0。要加密值\(m\)(0或1)，请生成一个较大的随机值\(R\)(通常比\(p\)还要大)和一个较小的随机值\(r\)(通常比\(p\)小得多)，然后输出：
要添加两个密文\(ct_1\)和\(ct_2\)，只需添加它们：\(ct_1+ct_2\)。要把两个密文相乘，你再一次...。将它们相乘：\(ct_1*ct_2\)。我们可以证明同态性质(加密的和是该和的加密，对于乘积也是如此)，如下所示。
\[ct_1=R_1*p+r_1*2+m_1\]\[ct_2=R_2*p+r_2*2+m_2\]。
\[ct_1+ct_2=R_1*p+R_2*p+r_1*2+r_2*2+m_1+m_2\]。
\[(r_1+R_2)*p+(r_1+r_2)*2+(m_1+m_2)\]。
其形式与密文\(m_1+m_2\)完全相同。如果您解密它，第一个\(mod\p\)删除第一个项，第二个\(mod\2\)删除第二个项，剩下的是\(m_1+m_2\)(请记住，如果\(m_1=1\)和\(m_2=1\)，则2将被吸收到第二个项中，而您将只剩下零)。所以，瞧，我们有加法同态！
\[ct_1*ct_2=(R_1*p+r_1*2+m_1)*(R_2*p+r_2*2+m_2)\]。
\[(r_1*R_2*p+r_1*2+m_1+r_2*2+m_2)*p+\\(r_1*r_2*2+r_1*m_2+r_2*m_1)*2+\\(m_1*m_2)\]。
这只是展开上面的产品，并将包含\(p\)的所有术语组合在一起，然后是包含\(2\)的所有剩余术语，最后是消息的产物。如果您解密，则\(mod\p\)会再次删除第一个组，\(mod\2\)会删除第二个组，只剩下\(m_1*m_2\)。
但是这里有两个问题：第一，密文本身的大小增加了(乘法时长度大约翻了一番)，第二，在较小的\(*2\)项中的噪声#34；(通常也称为##34；错误#34；)也变得平方增大。有必要将此错误添加到密文中，因为该方案的安全性基于近似的GCD问题：
如果我们转而使用精确的GCD问题，打破这个系统将会很容易：如果你只有一组形式为\(p*R_1+m_1\)，\(p*R_2+m_2\)...的表达式，那么你可以使用欧几里得算法来有效地计算最大公约数\(p\)。但是，如果密文只是\(p\)的近似倍数，并且有一定的误差，那么提取\(p\)很快就变得不切实际，因此该方案是安全的。
不幸的是，该错误引入了固有的限制，即如果将密文彼此相乘足够多次，错误最终会增长到足以超过\(p\)，并且在这一点上，\(mod\p\)和\(mod2\)步骤相互干扰，使得数据无法提取。这将是所有这些同态加密方案的固有权衡：从有错误的近似方程式中提取信息比从精确方程式中提取信息困难得多，但是当您对加密数据进行计算时，添加的任何错误都会迅速增加，从而限制了在错误变得不可抗拒之前可以进行的计算量。这就是为什么这些方案只有几分同态的原因。
这个问题有两种解决方案。首先，在许多有些同态的加密方案中，有一些巧妙的技巧可以使乘法只增加一个恒定因子的误差(例如，1000倍)，而不是平方。将误差增加1000倍听起来仍然很多，但请记住，如果\(p\)(或其在其他方案中的等价物)是300位数字，这意味着您可以将数字彼此相乘100倍，这足以计算非常广泛的计算类别。其次，还有克雷格·金特里的自举技巧。
假设您有一个密文\(ct\)，它是密钥\(p\)下的某个\(m\)的加密，这有很多错误。其想法是，我们通过将密文转换为另一个密钥\(p_2\)下的\(m\)新密文来刷新密文，其中该过程清除旧错误(尽管它将引入固定数量的新错误)。这个把戏很巧妙。\(p\)和\(p_2\)的持有者提供引导密钥"；，该密钥由密钥\(p_2\)下的\(p\)位的加密以及\(p_2\)的公钥组成。然后，对以\(p\)加密的数据进行计算的人将获取密文\(ct\)的位，并在\(p_2\)下单独加密这些位。然后使用这些密文在\(p\)下同态计算解密，并得到单个比特，该比特将在\(p_2\)下进行\(m\)加密。
这是很难理解的，所以我们可以这样再说一遍。解密过程\(dec(ct，p)\)本身是一种计算，因此它本身可以被实现为将\(ct\)的位和\(p\)的位作为输入，并输出解密的位\({0，1}中的m\)的电路。如果某人有一个在\(p\)下加密的密文\(ct\)，一个\(p_2\)下的公钥，\(p\)在\(p_2\)下加密的比特，那么他们可以同态计算\(dec(ct，p)=m\)"；，然后得到在\(p2\)下加密的\(m\)。请注意，解密过程本身会清除旧错误；它只输出0或1。解密过程本身是一个包含加法或乘法的电路，因此会引入新错误，但此新错误并不取决于原始加密中的错误数量。
但是.。这里有个圈套。在如上所述的方案中(使用循环安全或不使用循环安全)，错误爆炸得如此之快，以至于即使是方案本身的解密电路也难以承受。也就是说，在\(p_2\)下加密的新\(m\)已经有太大的错误，以至于它不可读。这是因为每个与门都会使错误的位长翻倍，所以使用d位模数(P)的方案只能处理少于(log(D))次乘法(串联)，但解密需要在由这些二进制逻辑门组成的电路中计算\(mod\p)，这就需要在一个由这些二进制逻辑门组成的电路中计算\(mod\p)。超过\(log(D)\)次乘法。
Craig Gentry想出了一些巧妙的方法来解决这个问题，但可以说这些方法太复杂了，无法解释；相反，我们将直接跳到2011和2013年的更新工作中，以不同的方式解决这个问题。
为了更进一步，我们将介绍Brakerski和Vaikuntanathan在2011年引入的一种不同类型的某种程度上的同态加密，并展示如何引导它。这里，我们将不再将密钥和密文作为整数，而是将密钥和密文作为矢量。给定密钥\(k={k_1，k_2....。K_n}\)，要加密消息\(m\)，需要构造一个向量\(c={c_1，c_2...。C_n}\)使得内积(或点积)\(<；c，k>；=c_1k_1+c_2k_1+...+c_nk_n\)模为某一固定
在本例中，我们设置了模数\(p=103\)。点积为3*2+14*71+15*82+92*81+65*8=10202，(10202=99*103+5)。5本身当然是\(2*2+1\)，所以消息是1。请注意，在实践中，密钥的第一个元素通常设置为\(1\)；这使得为特定值生成密文变得更容易(看看是否能找出原因)。
该方案的安全性是基于一个被称为错误学习(LWE)的假设，或者，用更专业但也更容易理解的术语来说，就是求解有错误的方程组的难度。
密文本身可以看作一个等式：\(K_1c_1+...。+k_nc_n\约0\)，其中键\(k_1...。K_n\)是未知数，密文\(c_1…。C_n\)是系数，由于消息(0或1)和误差(对于某些相对较小的\(e\)而言\(2e\))，等式只是近似的。LWE假设确保即使您可以访问许多这样的密文，也无法恢复\(k\)。
很容易验证加密是可加性的：如果\(<；ct_1，k>；=2e_1+m_1\)和\(<；ct_2，k>；=2e_2+m_2\)，则\(<；ct_1+ct_2，k>；=2(e_1+e_2)+m_1+m_2\)(这里的加法是模\(。更难的是乘法：与数字不同，没有自然的方法将两个长度为n的向量相乘为另一个长度为n的向量。我们能做的最好的是外积：一个包含每个可能对的乘积的向量，其中第一个元素来自第一个向量，第二个元素来自第二个向量。也就是说，\(a\o乘b=a_1b_1+a_2b_1+...+a_nb_1+a_1b_2+...+a_nb_2+...+a_nb_n\)。我们可以使用方便的数学恒等式(<；a\otime b，c\oTimes d>；=<；a，c<；*<；b，d>；\)将密文相乘。
给定两个密文\(c_1\)和\(c_2\)，我们计算\(c_1\o乘以c_2\)的外积。如果\(c_1\)和\(c_2\)都用\(k\)加密，则\(<；c_1，k>；=2e_1+m_1\)和\(<；c_2，k>；=2e_2+m_2\)。外部积\(c_1\ox c_2\)可以看作是\(k\o次k\)下的\(m_1*m_2\)的加密；我们可以通过查看尝试用\(k\o次k\)解密时会发生什么来看到这一点：
\[<；c_1\o倍c_2，k\o倍k>；\]\[=<；c_1，k>；*<；c_2，k>；\]\[=(2e_1+m_1)*(2e_2+m_2)\]\[=2(e_1m_2+e_2m_1+2e_1e_2)+m_1m_2\。
因此，这种外部产品的方法是有效的。但是，正如您可能已经注意到的，这其中有一个问题：密文和密钥的大小呈二次曲线增长。
我们用重新线性化的程序来解决这个问题。私钥的持有者提供作为公钥的一部分的重新线性化密钥，您可以将其视为\(k\)下的\(k\oox k\)加密。其想法是，我们将这些加密的\(k\ox k\)片段提供给执行计算的任何人，允许他们计算公式\(<；c_1\ox c_2，k\ox k>；\)以解密密文，但只能以这样的方式返回，即输出在\(k\)下加密返回。
重要的是要理解我们这里所说的嘈杂加密是什么意思。通常，该加密方案只允许加密\(m\in\{0，1\})，而\(m\)"；的加密是一个向量\(c\)，使得对于某些小误差\(E)，\(<；c，k>；=m+2e\)是\(<；c，k>；=m+2e\)。在这里，我们重新加密任意的\(m\in\{0，1，2...p-1\}\)。请注意，该错误意味着您无法从\(c\)；完全恢复\(m\)；您的答案将偏离2的某个倍数。但是，事实证明，对于此特定用例，这是可以的。
重新线性化关键字由一组向量组成，当这些向量与关键字\(k\)内积(模\(p\))时，给出\(ki*k_j*2^d+2e\)形式的值(mod\(p\))，每个可能的三元\((i，j，d)\)对应一个这样的向量，其中\(i\)和\(j\)是关键字中的索引，而\(d\)是指数，其中\(2。P\)(注意：如果密钥的长度为\(n\)，则重新本地化密钥中将有\(n^2*log(P)\)值；请确保在继续之前了解原因)。
现在，让我们退后一步，再看看我们的目标。我们有一个密文，如果用\(k\ox k\)解密，得到\(m_1*m_2\)。我们需要一个密文，如果用\(k\)解密，得到\(m_1*m_2\)。我们可以用重新线性化密钥来做这件事。注意，解密方程\(<；ct_1\o乘ct_2，k\o乘k>；\)只是形式为\((ct_{1_i}*ct_{2_j})*k_p*k_q\)的项的大和。
我们的再线性化钥匙里有什么？一串\(2^d*k_p*k_q\)形式的元素，在\(k\)下进行噪声加密，表示\(p\)和\(q\)的每种可能组合！在我们的重新线性化密钥中拥有所有2的幂允许我们只需将2的幂\(\le log(P)\)相加即可生成任何\((ct_{1_i}*ct_{2_j})*k_p*k_q\)。13=8+4+1)加在一起表示每个\((p，q)\)对。
例如，如果\(ct_1=[1，2]\)和\(ct_2=[3，4]\)，则\(ct_1\o乘ct_2=[3，4，6，8]\)，且\(enc(<；ct_1\o乘ct_2，k\o倍k>；)=enc(3k_1k_1+4k_1k_2+6k_2k_1。
\(\color{green}{enc(k_1*k_1)+enc(k_1*k_1*2)}+\color{red}{enc(k_1*k_2*4)}+\)\(\color{Blue}{enc(k_2*k_1*2)+enc(k_2*k_1*4)}+\color{橙色}{enc(k_2*k_2*8)}\)。
注意，在重新线性化密钥中的每个噪声加密都有一些偶数误差\(2e\)，并且等式\(<；ct_1\o×ct_2，k\o倍k>；\)本身也有一些误差：如果\(<；ct_1，k>；=2e_1+m_1\)和\(<；ct_2+k>；=2e_2+m_2\)，则。Ct_1，k>；*<；ct_2+k>；=2(2e_1e_2+e_1m_2+e_2m_1)+m_1m_2。但是这个总误差仍然(相对)小(\(2e_1e_2+e_1m_2+e_2m_1\)加上来自实现密钥的\(n^2*log(P)\)个固定大小的误差)，并且误差是偶数的，所以该计算的结果仍然给出一个值，当与\(k\)内积时，对于某些"；组合误差给出了\(m_1*m_2+2e'；\)的值，所以该计算结果仍然是(相对)小的(2e_1e_2+e_1m_2+e_2m_1\)加上来自实现密钥的固定大小误差\(n^2*log(P)\)，并且该误差是偶数。
我们在这里使用的更广泛的技术是同态加密中的一个常见技巧：提供在密钥本身下加密的密钥片段(如果您刻意避免循环安全假设，则提供一个不同的密钥)，以便对数据进行计算的人可以计算解密等式，但只能以输出本身仍然加密的方式进行计算。它在上面的引导过程中使用过，在这里也使用过；最好确保您在头脑中理解这两种情况下发生的事情。
这个新密文的错误要大得多：t。
.