本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。
上一期，我们了解了格密码学中的一个非常重要的primitive，即Trapdoor（陷门）。
如果快速回顾一下的话，我们学到最重要的莫非就是基于SIS与LWE的两个单向函数（OWF）的构造了。基于SIS的OWF 的构造如下：我们选择一个随机分布的矩阵。这个OWF的输入是一个短向量，输出则是：基于LWE的OWF 的构造是这样的：我们同样选择随机分布的。这个OWF的输入是一个任意的向量，与一个在噪音分布空间内的噪音向量，输出为：如果我们比较这两个OWF的输入与输出空间之间的映射的话，我们会发现基于SIS的OWF是满射（surjective）的，而基于LWE的OWF是单射（injective）的。我们还讲到了这两个OWF，如果我们有了Trapdoor构造出了对应的反函数，那么这两个反函数输出的特点也会和原本的OWF相对应。会输出很多种符合要求的解的一个高斯分布，而则只会输出一个唯一的解。随后，我们对Lattice中的Trapdoor到底长什么样子做了一个简单的探索：看到了所谓的Type 1 Trapdoor其实就是OWF对应的Lattice 的一组好的基向量（good basis），符合了短并且近似垂直的特性。基于此类Trapdoor，我们还大概了解了一下如何解决格中的一些难题（比如CVP）。
上期的最后，我们抛砖引玉介绍了一下Type 2 Trapdoor的存在以及它的各种优点。这一期我们就来看看Type 2 Trapdoor到底是什么。构造Trapdoor：第二类格陷门（Type 2 Lattice Trapdoor）
我们上期提到过，第一类格陷门是基于格本身的几何特点来构造的。虽然理解起来比较容易，但是实际上构造起来并不现实。
第二类格陷门是Micciancio与Peikert在MP12中提出的一种新的陷门构造。这一类的构造并不依靠几何结构，而是依靠对于矩阵的随机分布这一属性的更深理解。我们都知道，如果想要获得一个平均随机分布（Uniform Random）的随机矩阵，我们只需要平均随机地取个随机数，然后放进矩阵里就完成了。但是这并不是唯一的构造平均随机分布矩阵的方法。我们可以在随机选取的矩阵上再叠加一些别的东西，比如说任意的另一个矩阵，最后得到的叠加仍然是随机分布的！一个很简单的例子就是One-Time Pad（OTP）流加密算法。在OTP中，我们随机生成一段密钥，并且通过XOR叠加到原本的原文上，最后得到的密文也是呈随机分布的。这一随机分布的特性导致了OTP系统的安全性。同理，我们第二类格陷门的思路一样——我们在矩阵中引入一些特殊的结构，使得它具有一些方便我们构造Trapdoor的能力，然后通过随机分布的这一特性把这一特殊结构给掩盖起来，这样看到的人，并不知道这个矩阵是真随机生成的，还是通过我们的Type 2 Trapdoor的方法生成的了。我们先不用担心这里的Trapdoor到底长什么样子，因为我们的最终目标是构造描述过的两个OWF 的反函数。拥有了Type 2这一特性之后，MP12指出，我们可以通过非常简单的三个步骤来构造出我们想要的反函数。接下来，我们来看看MP12是如何尝试构造反函数的。其中一共分为三步：
- 选择一个构造非常简单的Gadget Matrix（工具矩阵），并且基于此矩阵构造出同样的函数。在此过程中，因为的特殊构造，我们可以非常轻松的得到并且计算。
- 通过上述描述的随机分布的特性，我们把“嵌入“到随机矩阵中，并且得到对应的Trapdoor矩阵。表面上看是呈平均随机分布的，但是只要我们知道的值，我们就可以通过非常简单的矩阵相乘与线性变换，从还原到。
- 最后，我们根据第二部构造的这一特点构造出我们想要得到的反函数。
下面，我们就来逐步详细的走一遍，复现这一过程。我们知道，原本的都是单向函数，是因为函数中包括的矩阵是呈平均随机分布的。我们的第一步就是弱化这个矩阵——能否我们选择一个特殊结构的矩阵，可以打破这个矩阵构造成的与函数的单向性。
这里说的特殊矩阵，其实就是我们称呼的Gadget Matrix（工具矩阵）了。工具矩阵并不是什么复杂的东西，其实就是一个提前选好公开，并且结构非常简单的矩阵。为了更方便理解，我们不妨先来看看这个矩阵的第一行——我们也可以称之为Gadget Vector（工具向量）。为了方便计算和理解，我们这里定义模组为。这个向量其实就是依次排列的2的幂，结构非常简单。这里的就是一个中的数值，我们可以理解为是原的中的输入向量中的一个元素。
这个迷你版的单向函数其实和完整版的结构一样，只是我们取了问题矩阵中的一行，缩小了输出的维度而已。由于工具矩阵的特殊构造，我们会发现，我们这里构造的这两个“迷你单向函数”一点也不单向。不仅如此，我们可以很容易的从输出的结果还原出原本的输入。我们首先来看一看基于LWE的。如果我们把向量的具体构造带入进表达式中，那么这个求解的反函数可以被表达为：换句话说，我们这里的目标就是基于这么一系列个取值还原出原本的来。
由于我们之前定义了，所以中的所有数字都可以被 bits来表达。我们先来看最后的一项。因为是一个 bits的数字，所以乘上了就可以理解为把整个数字往左left shift了位，即。这样就等于是我们把原本的的最低位一下子往左挪到了最高位上，然后剩下的其他位上都是0！随后，虽然我们还是会加上一个噪音，但是我们知道噪音的取值空间远远小于，所以加上这一个噪音就并不会改变我们最高位上的值。这样一来，我们就可以靠观测的最高位上的数值，就能知道的最低位啦。现在我们依靠这个方法成功的提取出了，接下来我们就看下一项。我们发现，其实这就等于是把的值往左挪了位，即。这样的话，原本的倒数第二位会被挪到最高位上，然后会跟着被挪到第二位上。因为我们已经推测出的值了，这个时候我们只需要把从我们的表达式中减去，即减去，我们就可以得到和上面一样的表达式，然后通过观察最高位的值推出了。
继续使用这个算法依次的处理所有的项之后，我们也就成功的还原出了这个-bit数字的每一位，从而还原出了。这也就是反函数的全貌了：输入一个项的乘积结果，用上述的算法还原出格bits，然后重组成输出。这里我们观察一下噪音的上限：只要噪音的取值上限不超过，即不会干扰最高位上面的值，那么就不会影响我们的反函数算法了。因为我们定义了，所以转换到这里的话，噪音的的取值范围则不能大于。这一上限和LWE问题中对于噪音的分布上限的要求是一样的。在LWE中，，。解决了LWE的迷你单向函数，接下来我们来看看基于SIS的迷你单向函数。我们知道函数是一个满射、有碰撞存在的函数，所以对应的我们的反函数应该可以输出一个高斯分布的解并且使得：这里的是一个中的数字。现在我们来尝试找到符合这一要求的。一看到这个问题，我们马上可以想到一个思路：因为正好是由2的幂组成，所以很理所当然的我们就可以直接把这个数字分解成个bits，然后每一个bit正好对应向量的一项，就搞定了。但是我们需要注意到的是，虽然这个方法找到的符合上述的等式，但是这个算法是deterministic（确定）的！这也就代表无论运行这个算法多少次，我们最后都只会得到一模一样的。然而这样的输出并不符合我们之前所期待的高斯分布的要求。那么到底要如何生成我们所希望的高斯分布呢？我们这里介绍一种最简单方法：穷举法（brute force）。因为向量是一个已知的结构，并且输入的的分布区域很局限，即 ，那我们完全就可以在看到之前穷举出所有可能的的值和对应的，然后再根据输出值把所有可能的输入都存起来。这样的话，当我们看到之后，只需要去找到可以生成的一系列输入，然后依次输出就可以了。因为我们需要一个高斯分布的结果，所以我们穷举的步骤如下：
一共需要重复多少次才可以结束穷举的过程呢？我们观察发现，给定任意随机的，那么得到对应的的结果在中大概也是均匀随机分布的。那么我们就可以把问题转化成：我们在空间中要取多少个随机数，才可以遍历整个空间？这其实就是一个经典的赠券收集问题（Coupon Collecting Problem），当我们生成个随机的之后，我们就可以大概率的相信整个输出空间已经被遍历啦。当我们完成这一步，构建出这个数据库之后，我们就可以非常轻松的反转了。穷举法虽然很容易理解，但是不幸的是复杂度太高了。一旦变得很大，那么这个算法马上就变得效率很低。MP12的原文中也提到了这一点，并且提出了一个更加高效的方法。具体的实现方法我们就不多说了，不过大概的思路就是从最低位开始“二进制”分解，不过我们选择每个bit的时候，我们不仅选择0或者1，而是我们在的coset（伴集）中随机选择。现在我们已经掌握了如何计算迷你版本的SIS与LWE的反函数。下一步，我们需要扩展这个定义到真正的SIS和LWE OWF。我们知道是由2的幂组成的，其实真正的工具矩阵构造大致相同，只是维度扩展成了行：因为的构造和大致相同，所以反函数的计算就很简单了：我们可以把分解成个平行的，然后依次求解之后，再按照应该的维度组合起来，就搞定啦。
知道了如何计算基于的SIS和LWE的反函数之后，我们距离构造真正的反函数已经不远了！其实现在的路线已经很清晰了，我们只要想办法可以从基于的SIS/LWE规约到基于的问题，那就可以使用我们上一步得到的反函数来计算结果了。之前有所提到过，构造SIS与LWE问题的矩阵其实就有一个要求，即这个矩阵需要看上去是平均随机分布的。我们可以尝试构造出如下的的结构：其中，是一个平均分布的维度的随机矩阵，是一个高斯分布的维度的随机矩阵。
这样构造的是不是平均随机分布的呢？我们不妨先来了解一个定理，即Leftover Hash Lemma。LHL指出，如果我们选择的矩阵的维度中，只要，那么这两个矩阵的乘积的随机分布近似于平均随机分布：这样一来，我们在看回我们这里定义的。因为是平均随机分布的，所以也是平均随机分布的（因为矩阵是一个已知不变的常数矩阵）。再加上左半边平均随机选择的，我们就可以充分证明矩阵是一个平均随机分布的矩阵了！现在，我们拥有了一个看似是平均随机分布的，如果我们公布出去，没有人会知道这个矩阵究竟是随机生成的，还是通过我们这里的方法用生成的。更重要的是，一旦知道的值的话，我们就可以非常轻松的从还原到：这里的随机高斯分布矩阵，就是我们这个构造的Trapdoor了！如果不知道，那么就是一个纯随机生成的矩阵。但是一旦知道了的话，我们就可以很快速的把还原成原本的。第三步：从fA-1,gA-1规约到fG-1,gG-1
我们的Trapdoor构造大业终于要完工了。第二步完成之后，我们的矩阵就变成了一个拥有Trapdoor的特殊矩阵。
我们把拥有Trapdoor的放入原本的SIS和LWE的单向函数中。如果不知道Trapdoor的话，那么这两个OWF应该和原来一样，无法计算反函数。现在，由于我们构造了这个矩阵，所以我们也就知道Trapdoor 。接下来要做的，就是基于Trapdoor的特性，尝试构造原本不可能完成的反函数。和之前一样，我们都知道基于LWE的单向函数比较好对付，因为这个函数的单射特性导致了反函数只会有唯一的解。所以我们先来看看，怎么通过Trapdoor来求解LWE。
因为我们知道了矩阵的特殊结构与Trapdoor ，我们可以直接把LWE的结果乘上陷门矩阵：
我们观察得到的结果可以发现，这和我们之前的的结果非常相似。唯一不同的在于最后的噪音项，之前是，而现在是。然而，我们其实并不在乎噪音的具体数值，只要噪音向量的每一项的大小不超过的范围，那就可以还原出的值了。我们可以直接使用来计算：是不是非常简单？这也就是LWE构造的格密码学算法的特点，计算过程非常的简单并且优雅。解决了LWE之后，我们现在来看SIS的反函数。
我们在上一期的文章中讲到，因为有碰撞的存在，所以SIS OWF的反函数不会输出一个唯一的结果，而是一组结果的高斯分布。我们再回顾一下SIS反函数的定义：MP12中给出的这张离散高斯分布的图代表了这个反函数输出不同的值的可能性。越靠近中心，那么对应的概率越高。现在，我们已知了结果向量，我们可以首先通过工具矩阵下的SIS反函数随机的抽取一个符合要求的preimage ：然后，我们只需要计算这个preimage 和Trapdoor矩阵的乘积，就能得到我们想要的结果了：验证通过！这下我们构造的反函数就能够成功的生成的了。是不是大功告成了？不幸的是，我们这儿的反函数有一个巨大的问题。问题出在，我们这个反函数输出的值的随机分布又出了问题。但是不是我们之前已经确保的输出是随机高斯分布了吗？但是我们发现，一旦我们把乘上我们的Trapdoor 之后，整个随机分布又发生了改变。根据MP12中所述的，如果我们观察这个反函数输出的的Covariance（协方差）的话，我们会发现这个协方差会暴露我们的Trapdoor 的信息：这里的代表了原本的高斯分布的一个半径系数。这样的非标准高斯分布的协方差会导致的问题就是，如果我们利用这个Trapdoor生成了太多的反函数的解之后，别人就可以直接通过观测的分布猜出我们的Trapdoor来。这对于这个体系的安全性是致命的。如果我们希望反函数的输出为高斯分布的话，那么我们需要输出的的协方差为高斯分布的协方差，即。然而我们现在的和想要的还差一段距离。那怎么办？Peikert在2010年提出了pertubation method，即我们可以加入额外的随机数来补上缺少的这部分协方差。即然我们有了一个协方差为的高斯分布，我们只需要补上一个的高斯分布，两者加起来的话，仍然是一个高斯分布。这是因为高斯分布之间相互的卷积还会是高斯分布（Convolution of Gaussians）。这样一来，MP12提出了如下的修改方法，可以使得反函数输出均匀高斯分布的结果：
这样一来，我们就彻底搞定了SIS单向函数的反函数了。经过这三步构造之后，我们就成功的复现了MP12中的Lattice Trapdoor了！最后，我们再总结一下我们到底做了什么。我们了解了一个万能的工具矩阵。只要我们能够把问题规约到基于的SIS或者LWE上来，那么问题一下子就变得好解了。上期的时候介绍Type 1 Trapdoor的时候，我们提到了Type 2其实蕴涵了Type 1在里面。这其实就是因为如果我们的SIS与LWE问题都基于的话，我们就可以很快的找到一组对应的Lattice 的短基向量：这个短基向量矩阵其实就是的Type 1 Trapdoor了。这也就是说，其实Type 2 Trapdoor的精髓在于，我们掌握了一个随机的Trapdoor ，让我们可以把一个随机的SIS/LWE问题转化到基于的SIS/LWE问题上。然后由于我们已经知道了的Type 1 Trapdoor，我们就可以求解SIS/LWE问题啦。总的来说，要构造带有Trapdoor的SIS/LWE单向函数的话，我们只需要选取平均分布的和高斯分布的，随后构造，作为SIS/LWE的单向函数的问题矩阵。只要掌握了Trapdoor ，任何人都可以有效的计算这两个单向函数的反函数。这就是Lattice Trapdoor的全貌了。了解完Lattice Trapdoor这一强大的工具之后，我们下一期开始就可以来学习基于Trapdoor的一些进阶的Lattice体系：Identity-based Encryption（身份加密，IBE）。本文内容主要参考于IIT Madras的教授Shweta Agrawal（https://www.cse.iitm.ac.in/~shwetaag/）的讲座。
封面图来自unsplash，作者Shiebi AL
