本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。
前一段时间写完基于格的GSW全同态加密系统（FHE）后，笔者对格产生了很大的兴趣。由于上学期在学校上的CS355（高阶密码学）讲完FHE之后就结课了，所以还有很多关于格的知识没有讲到。正如开学的时候CS355第一节课上说的一样：对于其他专业的学生来说，这会是你们密码学方向学习的最后一节课。但是对于密码学方向的人来说，这将会是你们真正入门密码学的第一节课。
这节课结束之后，后面就没有系统性的课程了。在过去的两个月内，为了更加全面的学习格密码学，笔者只好去网上与各个学校搜刮讲座和课件，拼凑起来从头开始学习Lattice的基础定义和几大难题。对于格有一个大致的了解之后，就可以看懂更加进阶的东西，比如IBE、ABE、NIZK、Multilinear Map、iO等等。了解完一圈下来，不得不说格密码学真的是万能的一个密码学分支，可以基本上实现所有密码学的应用（Crypto-Complete）。
关于Lattice-based Crypto的入门知识，有兴趣的大家可以去看笔者的【Lattice学习笔记】这一专题。在这里就假设大家对格已经有一个大致的了解了。从这一期开始，我们开一个新的专题【格密码学进阶】，学习一下更加进阶的格密码学的算法和构造。
这一期，我们来看看格密码学中的一个非常重要的工具：Trapdoor Functions（陷门函数）。
Trapdoor Function（陷门函数）简介
Trapdoor Function（TDF），即陷门函数，是一个密码学中非常常见的一个基础工具。简单的概括一下的话，TDF就是一个普通的函数，即输入空间为，输出空间为。这个函数有两个非常重要的特性：1. 首先，如果只知道这个函数的本身，那么这个函数就是一个单向函数（OWF）。单向函数是什么意思呢，就是给定一个输入，我们可以非常快速（efficient）地计算。但是如果我们只能看到这个函数的输出的话，我们很难从这个值推算出原本输入的值来。2. 虽然OWF的定义在密码学应用上很有用了（比如可以构造出PRG、PRF、Hash Function等等），但是TDF更加特殊的属性是，在生成一个TDF实例的时候，我们会额外生成一个这个函数的一个Trapdoor 。如果不知道Trapdoor 的值，那么原本的TDF仍然是一个OWF。但是如果一旦有人知道了Trapdoor ，那么就可以直接打破单向性，即可以有效的从中还原回出来。Wikipedia上对于TDF使用了上述的一张图片来解释。理解起来很简单：从到很容易，但是从到很困难。但是如果知道了Trapdoor ，那么从到也会非常简单。TDF在密码学上的应用多不胜数，比如我们最常见的RSA加密算法就基于RSA的一个TDF。在RSA一开始的密钥生成的过程中，我们会生成一对加密和解密的密钥。我们可以基于这一对密钥来定义RSA的TDF：因为大整数的有限域（）中，已知的话，我们很难还原出一开始的。但是如果我们知道了这个系统的Trapdoor 的话，那么我们就可以直接计算然后还原出最初的来。其他的TDF也是类似的样子，我们在生成这个OWF函数实例的时候预先预留好一个“后门”，即Trapdoor，然后知道这个后门的人就可以轻松的打破单向性。
如果我们要把TDF的概念带到格中来的话，首先我们需要来看看，Lattice当中我们都知道哪些OWF的构造。
看过前面的一系列文章（尤其是Lattice学习笔记）的朋友们应该对此不太陌生了。这里我们再来重新回顾一下Lattice中的两大难题：Short Integer Solution（SIS）与Learning With Errors（LWE）。
首先我们先看SIS问题。SIS相对来说结构比较简单，我们需要随机生成一个矩阵作为公开的部分。然后SIS问题就是，给定，能否找到一个“短向量”（一般来说为了方便计算，我们会把短向量定义为每个维度都是一个bit的向量），使得：这样一个求解短向量的问题（即SIS），在格密码学中被公认是一个困难的问题。同理，我们可以根据SIS的难度来构造一个OWF :我们得到的这个函数被Ajtai在1996年被证明为是一个单向函数（OWF）。具体的证明可以参考【Lattice学习笔记】中的对应内容，简单的说就是求解可以被规约到在Lattice 的对偶格中求解CVP问题，而CVP又是另一个公认的格中难题。在选择的参数的时候，我们一般会把压的比较小，使得这个OWF是一个满射（surjective）的函数，这代表了会有多个不同的短向量，使得：这一满射的特性决定了SIS OWF一定会有碰撞（Collision）的存在。但是这个OWF还有另一个特殊的属性：它是抵抗碰撞的（Collision Resistant）。这代表了就算这个OWF存在碰撞，我们也无法有效的根据一个已知的，找到另一个对应的来。接下来我们看格中另一个难题，LWE。LWE问题具体的我们在之前的文章中很详细的描述过了，这里我们就跳过介绍直接讲定义。一个LWE问题实例包含了一个随机生成的矩阵，一个随机生成的向量，还有一个错误分布区间。一般为了方便理解，我们会把拆分为个随机生成的向量来看待。简短的概括LWE问题的话，那么就是带有噪音的内积问题。假设有一个未知的向量，我们的目标是猜出这个向量的值来。LWE问题给了我们一系列的随机向量，并且还给我们看这些向量和未知向量的带噪音内积：其中的噪音部分就是从噪音分布中随机选取的。我们一共可以看到格内积的值。如果用矩阵的方式来表示的话：如果给定了和一组有噪音的内积的话，LWE问题定义了从中还原出原本的位置向量是困难的。和上面的SIS一样，基于这个问题的困难性，我们可以开发出一个新的OWF出来：这个OWF的输出其实就是LWE中的本身了。因为LWE是困难的，所以我们就算看到了，我们也不能推算出这个OWF的输入来。所以根据LWE的困难度，我们就可以定义这个OWF的单向性了。相比起上面SIS需要依靠CVP问题的规约来完成证明，LWE的安全性证明简单了不少。LWE OWF的一个特性在于它是单射（injective）的。和满射不同，所有的LWE问题（只要各项参数选择符合要求）都有一个唯一的解。fA与gA的反函数与Preimage Sampleable Function（PSF）
了解完基于SIS的OWF 和基于LWE的OWF 之后，我们现在来尝试引入Trapdoor的概念。首先，我们先不要着急想Trapdoor到底是个啥。是个向量还是矩阵还是数字并不重要。我们先思考一下， 假如我们已经拥有了这么一个神奇的Trapdoor，我们可以做什么。现在我们的和已经满足了单向性的属性，即我们可以快速的计算这个函数，但是无法从函数的输出结果有效地还原出输入来。根据前面对于TDF的描述，如果我们已知了Trapdoor，那么理应我们就可以构造出这个OWF的反函数来。这样的话，上面描述的两种OWF构成的反函数分别会是什么样子的呢？基于LWE的的反函数最简单，因为它是单射的（即每个输出都有一个唯一的输入解），所以会输出唯一的一对满足条件的输入。基于SIS的就不太一样了，因为这个函数是满射的（即碰撞存在），所以应该会在所有满足条件的答案中，随机选择输出的一个。在安全性的考虑上，这个“随机选择”的过程必须要是一个高斯分布，并且反函数输出的应该需要和输入空间中符合要求的解的分布大致相同。上面的图就是Micciancio和Peikert在MP12这篇paper中对于的输出空间分布的一个大概的描绘。在MP12中，他们把满足这类分布的一对满射函数与其反函数称作为Preimage Sampleable Function（PSF）。具体是什么意思呢？其实很简单，这就是在说我们使用和可以生成同样的一组概率分布。如同图上所绘，我们首先使用：我们在中抽取高斯分布的随机向量，然后统计下来所有通过之后结果等于一个任意选择的向量的向量。随后，我们使用：我们随机的选择一个输出空间中的向量，然后使用这个反函数来还原一系列符合要求的输入。PSF的定义就是，我们使用上述两种方法生成的在概率上的分布是computationally相同的。也就是说，如果我们看到一组符合分布要求的，我们无法分辨这组随机的向量组合到底是选定随机的输入通过生成的，还是选定随机的输出通过生成的。
这个概念现在看起来可能比较晦涩，但是PSF的定义对于后续的构造十分有用，尤其是在证明基于格的NIZK的零知识属性上极为重要。这里留做一个悬念，等我们学完前序的内容后，再回来详细的研究这一点。构造Trapdoor：第一类陷门（Type 1 Lattice Trapdoor）
当我们了解完Lattice中最有名的两大OWF和他们对应的理想中的反函数的大致构造（和输入输出分布）之后，我们就可以开始实战构造Trapdoor了。
系统性的分类的话，Lattice Trapdoor大致分为两种。我们首先着重了解一下第一种：基于Lattice的几何构造形成的Trapdoor。
如果我们随机的生成一个Lattice（如上图所示），虽然格点是固定的，但是我们可以选取不同的基向量（basis vector）来描述这个Lattice。
一组代表了Lattice结构的基向量，其实具有好坏之分。好的基向量（good basis）可以让我们非常直观的求解很多格中的问题。然而坏的基向量（bad basis）则反之。我们首先选出这个格中最好的一组基向量。我们发现，这一组向量很短，并且几乎是相互垂直的。这两个属性代表了这一组基向量构成的Determinant的基础空间（Parallelpiped）具有近似于长方体的形状。在这种结构内，求解CVP问题是很简单的。假如我们拥有一个的任意的点，要找到距离这个点最近的格点，我们只需要看这个点到底在哪一个长方体（Parallelpiped）内，然后直接输出这个长方体中心对应的格点就可以了。我们可以选择两个不同的基向量作为这个Lattice的新的基。这一组基就没有之前的结构那么的完美：基向量之间靠的距离很近，并且长度也很长。现在我们基于这一组坏的基组成的Parallelpiped分割一下多维空间。我们会发现这些平行多面体的形状非常的狭长，所以上面描述的CVP的解法就不管用了。
比如说图中距离黄点最近的格点就是在它右下方的红点，但是这个黄点却坐落在它左上角的红点代表的Parallelpiped上。所以如果我们直接用上述的方法来解CVP的话，那么很大可能性我们会找错点，找到并不是最近的那个格点上。
基于我们上面的观察，我们可以发现Lattice系统中的一个不对称性：
如果给定了一组坏的基（bad basis），那么在这个基的格中的SVP、CVP、SIS等常见问题都是困难的。但是反之，如果我们给了一组好的基（简短、近似垂直），这些格中的问题就会变得非常好解决。
我们都知道，如果一个数学系统出现了如上的不对称性的话，那么我们就可以把这一特性拿来用做密码学。这也就是第一类格陷门的精髓了。这也就是说，对于一个Lattice 来说，我们可以尝试找到两种表述方式：1. 第一种方式就是一个随机的矩阵，也就是一组随机的（坏的）基。基于这个矩阵，我们可以轻松的通过线性组合这些基向量来构造出格点，但是无法从格点还原回我们原本的线性组合来。2. 第二种方式就是一个短矩阵，这个矩阵就是一组近似相互垂直并且短的（好的）基。基于这个矩阵，我们就可以快速的把格点拆分回原本的线性组合，甚至是求解一些格中困难的问题，比如SVP、CVP等等。对于来说，我们可以通过来快速的求解CVP然后找出。同理，对于来说，这一组短的基可以帮助我们成功的找到一组均匀高斯分布的。第一类格陷门基于几何上的特点，所以非常好理解。然而，给定一个随机选择的的话，到底该如何生成呢？这个问题在几何上就很难找到答案了。
所以一般来说，Type 1的格陷门是为了方便、强化我们对于Trapdoor的理解而存在的，但是构造Type 1的格陷门相对来说比较困难。虽然当我们得到了对应的之后，我们就可以很简单的计算，但是实际使用中，我们不会使用这一类的陷门。下一期：第二类格陷门（Type 2 Lattice Trapdoor）
了解完Type 1 Trapdoor之后，想必大家对于Lattice TDF的大致构造和工作方式应该有了个大概的了解了。然而，Type 1的问题在于这个Trapdoor矩阵的构造并不简单，所以对于我们真正构造使用Lattice TDF没有太大的帮助。MP12这一篇paper中，主要描述了他们构造的新一类的Trapdoor，即Type 2 Trapdoor。这一类的Trapdoor虽然并不是像Type 1一样的一组短的基向量，但是Type 2的Trapdoor和Type 1一样强大（可以轻松的构造反函数），并且更加高效。更加神奇的是，当我们拥有Type 2 Trapdoor之后，我们可以利用这个Trapdoor来构造Type 1 Trapdoor需要的短向量矩阵。所以等我们学会Type 2的构造之后，我们可以回头再看看Type 1是如何生成的。
由于篇幅原因，这一期就说到这里啦。我们下期再见。
本文内容主要参考于IIT Madras的教授Shweta Agrawal（https://www.cse.iitm.ac.in/~shwetaag/）的讲座。
封面图来自unsplash，作者Pat Krupa
