本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。
GSW即Gentry-Sahai-Waters全同态加密系统。在我的另一个专题【初探全同态证明】中，已经用了两三篇的篇幅详细介绍过GSW同态加密体系的原理与构造了。
然而在这里，我们重新回顾一下GSW的构造，并且探索一些除了FHE之外，GSW特有的新特性。这些特性对于我们探索后期的应用非常重要。
P.S. 本文主要内容均来自于Hoeteck Wee的一个FHE tutorial，其中用到的图片都来自于原文。
我们熟悉的FHE（全同态加密）系统，主要的属性分为两点：同态与加密。
其中，同态这一特性为整个系统的功能性（functionality），因为它可以同态的计算密文中的内容，得到新的密文，使得我们完成一定的功能。然而加密这一特性为安全性（security），因为它确保了密文中隐藏的原文不会被提取出来。
我们这里跟随之前类似的视角，先从功能性开始回顾GSW。Homomorphic Functionality
FHE的functionality属性，如果简单的概括的话，就是我们可以通过的密文同态计算某个function ，然后得到：
如果只考虑这一特性，我们可以在一开始找到一个很简单的例子：矩阵的特征值（eigenvalue）与特征向量（eigenvector）。我们假设这个系统中的“密钥”是向量。假如我们要加密某个值，我们只需要找到一个对应的矩阵使得：这里的就是密文了。我们可以很简单的发现，我们可以很简单的把不同的组合起来，同态计算其中的原文：如果我们总结一下这种表达形式的话，我们可以把要计算的部分用来代替：等式的左侧是我们直接通过密文结合生成的同态计算结果，而等式的右侧就是直接在原文上计算的结果。注意在这里，我们使用矩阵来表示密文，而不是平常会用到的，这样的notation和之前稍微不同。上面给出的构造，虽然实现了functionality，但是完全没有任何security。这是因为给定一个矩阵，我们可以很轻松的算出他的特征值与特征向量。
所以，第二步我们需要基于原本的构造加入一系列的噪声，使得我们没法通过推导出。要做的事情很简单，我们只需要在这个等式的左侧加入一定的随机噪声向量，使得原本的相等变成近似相等就可以了。我们这里并不需要过多的了解噪声的构造，只需要大概知道它存在的意义即可。加上了噪声的这个等式，一下子就变成了格问题中有名的LWE问题。如果我们想要从一个noisy的线性乘积样本中提取出原本的，这个问题被公认是困难的。接下来，我们快速的sanity check一下之前的同态特性。这是因为虽然中都带有一定的噪声，但是这些噪声都是有限的（small）。所以small + small = small，我们得到的结果也是一个有限噪声的密文。这是因为，当我们相乘与的时候，我们变相的在把中的噪声项乘以本身。因为并不是有限分布（small）的，所以最后得到的结果的噪声会变的不可控制。即然之前乘法失败的原因是因为的分布不是small的，那么假如我们把所有的矩阵都可以变成small的，那么问题就解决了。这样的话，我们就可以在噪声范围的允许下，同态的计算任意的函数：
回顾完了GSW的大致原理之后，接下来我们来看GSW在Lattice中的具体构造。首先，我们要把要用到的LWE问题（近似特征向量）设置好。我们选择一个随机的矩阵，以及一个随机的向量，还有small的噪音。我们可以把这三个元素组合起来，变成我们预期的大概结构：这里左侧的向量就是我们之前所提到的向量（即密钥）了。我们注意这里的乘法右侧，就是我们的矩阵（即密文）了。因为DLWE的难度告诉我们，的概率分布与一个纯平均分布的随机矩阵难以辨别，所以我们可以把这一部分作为一个OTP，遮盖住里面的原文。接下来，和我们之前说的一样，我们需要把矩阵的取值范围变小到二进制。这样一来，就可以满足我们之前提到的同态乘法的噪声分布要求。
为了能够把一个矩阵或者向量变成二进制态，我们需要引入一个二进制分解函数。这在介绍GSW的文章中我们详细描述过了，在这里就一笔带过。还对应着一个二进制的重组矩阵，并且满足了的属性。
注意这里G是一个矩阵。这也就代表了，二进制分解虽然很复杂（是一个函数），而重组回十进制只需要一个很简单的线性变换（即矩阵相乘）就可以做到。
这样一来，我们发现原本的矩阵被二进制分解了，所以每一个值都只能是0和1，满足了我们之前的要求。为了使得整个等式仍然成立，我们需要加入一个矩阵来重组分解之后的。因为原本的等式中额外加入了两项，我们接下来需要重新的调整一下与的定义，使得整个等式仍然保持一个的构造。在等式中，我们已经标注出了新的向量，即。随后，我们需要更新矩阵中的表达式，使得基于的等式成立：我们最后得到的这个等式，就是GSW加密系统的全貌啦。虽然看起来复杂，但是我们只需要记得最简单的表达形式就足够了：
接下来，我们来看一下GSW中进行同态计算时的噪声增长规律。当我们相乘两个密文的时候，我们有两种相乘的方法， 都可以符合之前定义的“small”。
第一种相乘的方法，是把全部进行二进制分解，然后再相乘，即：这样一来，等于我们是在相乘两个二进制矩阵。假如每个密文一开始的噪声level都是“small”，我们用这种方式同态计算之后，得到的噪声增长趋势则为：第二种相乘的方法则不太一样，因为GSW的乘法计算是不对称的（我们只需要考虑的大小），所以我们只二进制分解后面的，然后在进行下次计算前，再把密文分解一次：这样的话，我们等于是进行了一次噪声与small的相乘之后，然后再分解了一次，把噪声的分布又压回了small。这种方式下的噪声增长趋势为：我们发现第二种方法结合密文可以让噪声的增速减少很多！总结一下，当我们同态的计算密文的乘法的时候，比起把所有的密文都二进制分解了乘在一起，我们更应该依次计算，先分解一个，乘一次，然后再分解一次。这样更能控制住噪声的增幅，从而决定了modulus的大小。同样的FHE系统，计算同样的功能，却能带来完全不同的噪声增长。这是因为计算方案不同所导致的。
假如我们要同态的计算一个function ，其实有两种最常见的方案来实现它。第一种方案是最intuitive的方案，即用电路（arithmetic circuit）来表达，然后再用我们之前看到的加法与乘法的计算方法来同态计算它。然而电路带来的问题是，它是由各个逻辑门（gate）组成的。当我们提供输入之后，这些输入就会不断的在各个gate中计算，然后结果再流进下个gate进行下一步计算，组成一个gate的串联结构。这样就带来了一个问题：因为每一个gate都会变相的增大密文中的噪声，我们越往后的gate，所看到的输入的噪声就越来越大，然后在进行乘法的时候增加的噪声也会随之增大（因为噪声项也会影响乘积）。这个问题的根本原因在于电路本身的特性：我们不断的组合intermediate的计算结果（即计算到一半的结果）来生成最后的结果。假如我们拥有一个大小的电路，那么同态计算之后的结果的噪声也会是exponentially增长的，大概为：然而，我们计算一个“程序”，其实还有第二种方法，即把它转换为一个Matrix Branching Program（MBP）。这在上一篇文章中有所提到，根据Barrington‘s Theorem【Bar86】，一个的电路，即深度在的电路，可以被转换成一个多项式大小的MBP。这个MBP的长度为即。MBP不同于电路的一个属性在于，我们计算一个程序是通过输入来“选择”一系列的矩阵相乘起来。因为我们选择的这些矩阵都是全新的（未被同态计算过的），所以等于是我们会相乘一系列freshly encrypted的密文。这一点确保了我们不会相乘两个噪声增长都很大的intermediate steps在一起，导致噪声更快的增长。所以如果我们基于MBP形式同态计算相同的程序的话，我们的噪声增长会是线性的，大概为：注意这里我们是大概的约束了一下噪音增长的幅度，并没有仔细的分析具体的噪声的展开式。不过通过初步的分析，已经可以看出来，GSW FHE在进行同态计算的时候，因为乘法计算中噪声增长的asymmetry，我们可以巧妙的利用同一个程序的不同形态（即MBP）来最大程度额抑制噪声增长。当我们使用MBP来进行同态计算之后，因为噪声的增长和电路的深度是多项式关系，所以我们选取的LWE modulus 和噪声范围也是多项式关系。对于这种参数关系的LWE问题的难度，我们称之为polynomial hardness。接下来，是这一篇文章最重要的部分，我们要基于之前给出的GSW加密关系式，推导出GSW中最具有代表性意义的Key Equation。
我们在这篇文章的最初提到了最简单的“FHE”，使用一个矩阵Eigenvector的属性构造的体系。这个体系只实现了Functionality，但是没有实现Security。我们在推到GSW的关键等式之前，不妨再重新看一下基于Eigenvector的这一构造。
首先，基于Eigenvector的特性，我们知道这个系统的正确性，即“密文”可以被成功还原为原文：我们重新变换一下这个等式，把所有含有的部分挪到左边：为了使得项的维度符合等式，我们把这一项乘上了identity matrix 矩阵。同理可得，我们可以基于这一等式，推导出同态计算之后的结果的正确性：随后，基于这个体系，我们还可以得到一个更加广泛的Lemma II，并且其中包含了Lemma I中的内容。Lemma II指出，给定任意的密文矩阵，与任意的加密原文和同态计算的函数，我们都可以找到一个对应的矩阵，使得可以满足：我们观察发现，Lemma II直接包含了Lemma I的内容。我们可以在等式的两侧都乘上：根据我们之前的得到的等式，我们会发现左侧的乘上整个矩阵都会等于0。相同的，在右侧的乘上对应的矩阵也会等于0，所以等式成立。接下来，我们就需要证明，在我们之前看到的加法和乘法的例子中，我们真的可以找到这样的矩阵，满足这一等式。
首先来看加法。假如我们拥有这两个矩阵，我们计算加法的方式就是把他们相加起来。对应的，我们也可以找到矩阵：其次，我们来看乘法。同样，假如我们计算的同态乘法，那么我们直接把他们相乘起来即可。对应的也很简单：因为我们找到了乘法和加法对应的矩阵，所以我们可以把这两个矩阵根据实际要计算的电路构造组合起来，构成进行任意计算的矩阵了。
接下来，我们开始尝试推到最关键的等式，即代表GSW的Key Equation。
由于之前我们都是在特征向量体系上推到的，现在我们需要把它转换成近似特征向量体系（即GSW）。换句话来说，我们需要在这个系统中把原本的一部分等式变成近似等式，然后把矩阵替换为矩阵。如果转换成上述Lemma I中的格式，那我们可以得到：接下来，我们改变Lemma II。我们这里除了需要把矩阵替换成之外，还需要额外的约束是一个短矩阵，取值范围为“small”：为什么矩阵需要是短的呢？这是因为我们需要约束它来控制噪声的增长范围。我们可以同样的在等式的两侧乘上：因为根据修改过后的Lemma I，我们知道乘以之后会得到一个近似于0的结果（即噪声）。所以在这里我们等式的左侧和右侧都会得到一个的噪声。为了使得等式成立，我们不得不选择一个短的矩阵，使得左侧的噪声乘以之后，取值范围不会过多的增长，仍然可以等于右侧的噪声取值范围。
接下来，我们和之前一样，尝试证明这一Key Equation的正确性。
首先，加法和之前是一样的，原本的矩阵是由两个identity matrix构成，自然是small的：唯一不同的是乘法，因为我们需要保证相乘的时候，是small的，所以我们需要额外的加入一次二进制分解，使得满足解密的正确性：此时，我们的矩阵仍然是small的，符合Lemma II的要求。
实现了加法与乘法之后，我们就可以跟之前一样，扩展到同态计算任意的functionality 了。
我们在这里再次列出GSW的Key Equation：
这一行等式直接概括了GSW中所做的同态计算的根本原理，并且给了我们一个非常好的视角来重新理解GSW的构造。
乍一看这个公式，似乎我们并不能用来直接做什么。其实这个Key Equation最重要的地方在于，它直接告诉我们，GSW拥有两种不同的计算functionality 的方法！假如我们拥有一系列的密文，然后我们想要在密文上计算某个的话，第一种计算方法是最直观的，就是我们之前就了解的GSW的同态计算。我们只需要把要计算的拆分成一个个小的加法与乘法，然后再根据之前我们学习的方法来同态的计算它们，最后生成密文。这种方法的好处在于，即使我们不知道密文中加密的内容，我们也可以直接通过结合密文来计算。然而，第二种方法是这里的Key Equation额外告诉我们的：假如我们已经知道了这些密文加密的的值，那我们就可以通过推导出等式左侧的矩阵来计算出相同的出来！这也就是说，我们可以通过两种方法来生成同一个密文的同态计算结果。其中一种方法只需要用到密文本身，而另一种方法则需要用到其中的原文。在FHE系统中，我们之前即使不知道这个Key Equation的存在，仍然正常的学习了同态计算密文的方法。这是因为GSW Key Equation在FHE的应用场景中，我们只需要通过组合密文，计算出右侧的就足够了。等式左侧的的存在，只是为了整个FHE系统的correctness。之所以我们可以结合不同的密文同态计算某个functionality，正是因为这么一个矩阵的存在。
我们上期讨论【BGG+14】的ABE结构时，我们也提到了类似的概念：我们通过计算矩阵来签发密钥，随后使用类似于的线性变换在属性加密的密文上进行计算，得到一个类似于的结果，最后使用密钥来解密。在【BGG+14】的ABE中，等式右侧的部分我们用于密钥生成（keygen），而左侧的部分我们则用于解密（decryption）。最后，还有一个比较有趣的应用，即全同态签名（Fully Homomorphic Signatures，FHS），在【GVW15】中由Gorbonov，Vaikuntanathan与Wee提出。具体的应用方案和FHE差不多，我们假如签发了消息的签名，那么我们就可以同态的计算某函数，得到一个的签名。在FHS中，等式右侧的部分用于签名的验证，而左侧的部分用于签署新的签名。
这一期，学习的最重要的内容即GSW FHE的关键等式（Key Equation）。这个关键等式高度的概括了这个体系的精髓，从而让我们能够基于这个系统派生出各种各样的应用来。
下一期开始，我们就来看基于这个Key Equation而产生的第一个比较高级的应用：基于格的非交互零知识证明（NIZK）。
封面图来自unsplash，作者Joshua Fuller
