2012年BIU密码学冬令营-01-格简介-第3部分

演讲视频简介

我们继续带来2012年BIU密码学冬令营，Lecture 01，Introduction to Lattice第3部分的内容。第3部分更加烧脑，涉及到格中常用定理的介绍，以及格密码学中常用假设的介绍。

演讲视频信息

演讲视频字幕

我们首先来总结一下第一个小时讲解的内容。我们讲了格的基，讲了两个格基的等价条件，我们讲的第二个知识是格的基本区域。后面我们应该还会再讲到，基本区域是一个区域，如果把这个区域放在每一个格点上，那么所有这些区域连接在一起，可以完整覆盖整个平面。正如幻灯片上的这个图，以及图上的这些区域。基本区域还有一个等价定义，在一个基本区域中，不存在两个等价的空间点，基本区域只包含所有不等价陪集内的点集。我给大家讲解时借助了存储函数值的思想，但在Vadim的讲座中，我们在取点的时候更关心格点。我们不太关心点的实际位置，我们关心的是点在格中的相对位置。如果我们想存储点对应的函数值，我们只需要把点模平行多面体，然后存储这个点模基本区域后的函数值。一般把这个基本区域称为基本平行多面体，因为这个名字更形象一些。

我们开始讲解下一个知识点。我们再来看一下这个图。我看到有些朋友们开始记笔记了，非常好。我们来看看左边这个正方形。现在我们考虑这个正方形的面积，正方形的面积是1，因为1乘以1，很简单。但是右边这个平行四边形的面积是多少？大家知道在代数学里面怎么求这个面积吗？你可以计算一下，这个面积同样也是1。如果你认真思考一下的话，就会发现这不是一个巧合。还记得基本区域的定义吗？我们定义基本区域的方法是把这个区域放在每一个格点上，用格点来平移这个区域，这样我们就可以覆盖整个空间了，差不多是这个意思。如果你稍微想一想的话，这个定义也意味着，这两个区域的面积必须是一样的。证明方法是在平面上取一个非常大的区域，并且假设在这个区域中，你有上亿个格点，而且这个区域中还有很多类似这样的小区域。这样你就分别用左右两个区域来覆盖整个大区域，他们覆盖的都是同样的大区域，所以它们的面积应该一样。因为上亿个小区域都能覆盖同样的大区域，我们可以取很多很多这样的小区域，这样面积就和区域的形状没关系了，可以忽略区域的形状。我们可以取很多很多小区域，然后用不同的小区域覆盖大区域，他们面积都是一样的。

不知是否有人已经注意到，这对于平行多面体来说也是一样的。大家稍微想一下，一般来说，对于任意平行多面体这个性质都成立。即使所取的平行多面体是个天马的形状，我们也会直接得到天马的面积是多少，可以直接计算面积值。对于平行多面体来说，其体积是很好计算的。我也可以直接得到面积值，因为它是一个基本区域。Vadim会提到另一个特性，你可以把一个平行多面体内部的点一一映射到另一个平行多面体上，这形成一个平行多面体到平行多面体的一对一映射。模这个平行多面体和模另一个平行多面体，本质上是一模一样的，我们很容易找到方法进行相互转化。本质上，这些平行多面体包含的信息是一样的，我们后面会精确定义这一点。我很高兴能把Vadim要讲内容都讲了，不过不会的。

这就是我下面要定义的一个概念了，叫做行列式。什么是行列式？本质上说，行列式就是平行多面体的体积，它告诉了我们格点的密度。那么什么是行列式？行列式是定义为基矩阵的体积，也就是基向量所构成多面体的体积。所以格 的行列式，定义为由基 生成的平行多面体的体积，也就是 的绝对值。

如果你观察一下这个定义，你可能先会问个问题：为什么我们要定义这么一个标量呢？因为我们实际上在用基的性质来定义一个标量，而我们知道一个格有很多的基，所以为了让这个定义有意义，我们需要保证，对于不同的格基，其标量值都是一样的。实际上标量值确实是一样的，我们可以证明。

证明思路如下。我已经讲过，两个基生成了同一个格，当且仅当一个基可以用另一个基乘以幺模矩阵得到。所以我就有了另一个基，用 表示。而 的行列式等于 和 的行列式相乘，也就是 的行列式乘以 的行列式，同样要取绝对值。但是根据定义，幺模矩阵的行列式值为正负1，所以可以把这一项拿掉，得到 的行列式等于 的行列式。

这个定义很好，格行列式的定义很准确。行列式还有很多有趣的意义，它告诉了我们格点的密度值。如果行列式很大，意味着格点比较稀疏，点与点之间有更多的空隙。具体原因还是要从线性代数角度考虑。一个格的行列式，等价于列向量构成矩阵所对应的平行多面体体积。如果有人忘了的话，回想一下，行列式所求的就是所对应的平行多面体的体积。而我前面讲到，平行多面体 就是格的一个基本区域，所以平行多面体的体积正是 的行列式，因此也是格的行列式。行列式表示格点的密度，这是我们可以计算得到的有关格的一个性质，我们可以计算格点的密度情况。很容易计算行列式的值。如果你有一个格，你很容易指出这个格的格点密度情况。我会时刻提醒某个定义计算的难易程度，因为这是格密码学的一个重要内容。这就是行列式的概念。

我要讲的下一个概念是连续极小。这就不再是一个很直观的概念了，这是数学家早期研究的一个概念，Minkowski主要研究这方面的内容。我在这里会给大家介绍Minkowski定理。那么，什么是连续极小？我们用 表示第一个连续极小值。是 中最短向量的长度。如果我们有一个格，的表示格的最短向量长度。

当然，这种定义方法忽略了连续极小的两个隐含意义。第一个忽略的隐含意义，也就是第一个错误是，我问的是最短向量。实际上最短向量永远是0，0永远是格中的一个向量。我们当然不能把0考虑进来，所以我们要求是非0向量。第二个隐含意义是，我们用欧几里得范数来表示距离，也就是 距离。当然了，不一定非要用欧几里得范数，不过一般用欧几里得范数表示。当用非欧几里得范数时，会得到其他一些有趣的性质，不过现在我们只考虑欧几里得范数，最一般的范数表示方法。

我们还忽略了一些隐含意义，这个定义并不是很准确，有人能猜到吗？完全正确。我不应该用最短向量这个词，我应该用最短向量集合这个词，因为最短向量肯定不是仅有1个，至少有2个最短向量。因为如果你有一个最短向量的话，这个向量的负向量一定也是最短向量，其长度是一样的，而且负向量也一定是在格点中。在有些情况下，可能还有很多最短向量。比如 格。在 格中，我们有 个最短向量，每个轴上都有两个最短向量。不过人们一般统一称他们为最短向量，所以这么说也没问题。如果更准确些，我们应该称之为最短向量集合。

这就是 ，这就是第一个连续极小。你估计能猜到，还有其他的连续极小。我们用下述方法定义所有的连续极小： ，其中 的范围是从1到n，n表示格的维度。连续极小是类似这样的半径值。我们在 维下寻找半径值，我们寻找 个线性无关的向量。这个图中大家已经能看到最短向量了。你可以注意到，图中有两个最短向量。但没关系，这两个最短向量都不是 。 得用线性无关的向量表示，因此这是第一个向量，这是我们在二维空间中寻找两个线性无关向量时得到的第一个半径。这是一个向量，长度就是，向量的长度用表示。不是这个向量，实际在这里。这是我们找到两个线性无关向量时得到的格点。我们一般只关心，也就是最短非0向量。 是另一边的极限值了，是n个线性无关向量的半径。这时候你就得到了整个线性空间的基，不是格的基，而是整个线性空间的基，不过这两个是等价的。

下一个我们要讲解的概念…我们会经常用到这个概念，这是个非常有用的概念，实际上这是线性代数中的概念…在线性代数课程中你估计已经学过这个概念了。在格中，这个概念也是一样的，但是这个概念非常有用，与格的联系非常紧密。这是个什么概念呢？这个概念称为Gram-Schmidt正交化。相信很多人都听说过，这里我给大家复习一下，这个正交化过程是如何工作的，这对格非常有用。

我们有什么呢？我们有一个有序的向量集合，我们希望让他们正交。我们的方法是对每个向量做投影，在前面的向量上做投影。这是一个有序向量几何 。每次操作时，我们把一个向量投影到前面向量的生成空间中，所以向量的顺序起到了很重要的作用，这不是一个向量集合，而是有序向量集合。我们这里有 ，我们把 投影到 的正交空间中，所以会被平移到的正交空间上，差不多是这个样子。注意到不再是格点了，所以大家注意，这个处理过程不是一个格上的处理过程，这是一个线性代数的处理过程，而且令人惊讶的是， 不再是一个格点了，我们不能把它看作格点了。

这个定理非常有用。如果我们想把它写成线性代数的形式，写出计算 的方法是一个很棒的线性代数习题。 就是 。如果我们把第一个向量投影到前面向量的生成空间上的话，由于前面没有向量的，所以我们直接保留这个向量。但是的处理过程就有意思了。等于减去与的内积，然后再映射到…这等于减去在上的投影值，投影值写成了这样的形式。这就是投影到的值，再乘以后，除以范数的平方。

我们很容易看出这个公式的意义，作为一个练习吧。我们不用太多关注具体的公式，我们要关注的是，这个过程输出了一个正交向量集合，这个正交向量集合具有很多重要的性质。这里是两个向量，你可以想象一下三个向量的情况。比如第三个向量在这里，那么正交投影应该垂直于屏幕了。

这个过程与格的第一个关系是这样的，Vadim也会用到这个关系，有些人在预习这个讲座的笔记时估计已经看到了。第一个关系称为Gram-Schmidt基本区域。我给大家展示了很多基本区域，比如天马什么的。这是另一个基本区域，这个基本区域很有用，一般用于命题的证明。我们在格中选一个基，比如这样的一个基，这个基包含两个向量，这两个向量定义了一个基本平行多面体，也就是这个区域。我们知道这也是一个基本区域，如果我把这个区域放在所有格点上，那么就能把这个平面覆盖上。幻灯片上我只列了这些点，但是这个区域覆盖了整个平面。我现在取这个基的Gram-Schmidt正交基，你会最终得到两个向量， 和 ，或者说 和，其中不再是一个格点了。但我们考虑这个正交基生成的方盒，考虑这个方盒。这也是一个平行多面体，但是是由正交向量生成的，所以我称之为方盒。这也是一个基本区域，产生的区域是这样的，有点像砖块。这并不是巧合，不难证明这一定是个基本区域。Gram-Schmidt正交基可以生成一个基本区域，这有时候会很有用，在下一个讲座中我们会讲解这个基本区域的作用。

下一页幻灯片中我会稍微讲解一下它的作用，我们从数学的角度看看会发生什么，从数学的角度很容易体现它的作用。我们现在已经有了一种方法，可以通过基产生一个正交向量集，下一步我们可以把向量规范化，就得到了规范化正交向量集了，对吗？我们可以取任意一个格基，使用Gram-Schmidt正交化，得到正交基，然后在规范化这个正交基，这样我们会得到 除以 的范数，一直到 除以 的范数。这也是一个规范化向量集，它们也不是格点，它们也不需要是一个格点。这个基有什么好的性质吗？有时通过这个基思考一些定义和定理会很有帮助。这个基是 线性代数层面上的，不是格层面上的，它是 的一个基。这个基的好处在于，如果你把格基 写成这种基的形式，不仅列向量会被恢复为格向量，基又写成了基的形式。这样表述后，基就不再是一个正交基了，而是把一个正交基用 中的一个基旋转，这样就会得到一个非常好的形式。这样表示后，格基将成为上三角形式。这种表述形式非常有用，后面大家会看到，我们现在要证明里面的两个性质，这两个性质也体现了这种基表达方式的好处。这个表达方式本质上是，取 这个原始矩阵，然后对这个基做变换。本质上我在这个基的左边乘以一个正交矩阵，所以实际上我什么都没做，我只是把相同的基用 的另一个基表示而已，用一个正交基来表示，所以所有性质保持不变，而正交基表示空间旋转。

这会发生什么呢？举例来说，向量 非常简单。的第一个坐标是一个非0数，其他坐标均为0，这是因为根据正交变换定义， 就等于 ， 就在 的方向上。所以我们已经知道，只在第一个轴上有坐标。根据定义，第二个向量 是在第一个向量生成空间中的…我们往回看一下，这里，在和的生成空间中。我们可以这么解释，如果是二维空间的话，任何一个向量都在这两个向量的生成空间中。但是大家可以想象一下，在高维空间中情况是什么样子的。所以第二个向量中，第一个坐标是非0向量，第二个坐标就是，的范数就是第二个向量的第二个坐标。所以这只是同一个基的另一种表示方法，但这种表示非常方便。第一点是，用这种表示方法来证明，Gram-Schmidt方盒是一个基本区域的话，大家会发现证明很容易。我会给大家两个引理，用这两个引理就可以证明出来。我要提醒大家的是，这种表示方法有时也被称作QR分解。如果你在线性代数课程中听过的话，QR分解就是将一个矩阵正交化。这是Q部分，R部分是一个上三角矩阵。当把QR分解用到格基上时，他就有了更为特殊的意义。

我现在要证明两个结论。第一个结论很容易证明。这个结论称，由 生成格的行列式，等于所有 范数的乘积。这个问题你可以这么看，这是一个上三角矩阵，上三角矩阵的行列式等于对角线上元素的乘积，所以我们就得到所有范数的乘积。很容易证明这个结论，有时候会用得到这个结论。

第二个结论可能更有用些，用处更大。这个结论称 ，回忆一下，是第一个连续极小，也就是最短非零向量的长度，最短也不会小于最小的那个范数长度。我们盯着这个矩阵，看看怎么证明这一结论。回忆一下，什么是格？格是这个矩阵列向量的整数组合，所以这个矩阵的列向量生成了格。这种表示方法只是把基旋转了一下，本质上没有改变基。想象一下这就是我们的格，由矩阵列向量的整数组合生成的格。我们第一个要注意的是，这是一个上三角矩阵，所以我们首先要注意到的是，如果在最右边的列向量使用一个非0系数，那么这个格向量的长度最短也至少为 的范数。这是因为最右边向量的最后一个坐标，如果取这个向量的话，取一个非0系数，那么最短向量的最后一个坐标长度至少为的范数，向量的范数中一定会含有最后这个坐标的范数值，即使所有前面的坐标都可以互相消去，都变成0。这很容易，如果最后一列不为0，最后一个系数取的不是0，那么很容易得到这个结论。如果是这种情况，我们知道最短向量长度至少为 ，所以第一个连续极小值最小也不会小于 。那么如果是0会怎样，如果最后一个系数是0呢？我们考虑下一个坐标。如果下一个坐标是非0，现在最后一个是0了，下一个坐标非0，下一个坐标就是这个坐标了，也就是，至少是这个长度的绝对值，结论也成立，以此类推。

我们实际上在证明什么？我们在对列取任意非0系数，取列的整数组合，对最后一个列取非0系数，这样最后一个列会为第一个连续极小提供一个范数，第一个连续极小要要大于的范数，这就完成了证明。总能找到一个非0系数，使得最短非零向量中的某一项不能被消掉，因为这是一个上三角矩阵，肯定有一项消不下去。这个结论非常基础，但这个结论非常好，因为我们从这个结论得到了 的一个下界，用其他方法很难从格基中得到的下界，所以我们可以这样得到一个下界。而且，这个结论还和LLL算法有一定的联系。这就是Gram-Schmidt正交化了。

我们还可以证明其他一些有趣的结论，这就是Minkowski定理。我们先从一个基本定理讲起，这个定理是由Blichfeld提出的。Blichfeld定理告诉我们，考虑任意一个格，现在我们用Λ表示格，而不用L，但这两个符号都表示一个格，只是表示方法不一样而已。选一个格Λ，令S是任意一个集合，要求S的体积大于格的行列式。这个定理说明，在集合S的内部，一定能找到两个点，这两个点的差是一个格点。注意我们这里要求集合S的体积大于格的行列式，因为如果我们任意取一个基本区域的话，基本局域中可能找不到这么两个点，使得点的差值为一个格点，因为在基本区域中有且只有一个格点，所以如果取基本区域的话，这个结论不成立，所以我们需要集合S的体积大于行列式。

这就是这个定理的证明方法，我们用几何方式来证明这一点。我们选一个袋鼠，这是一个很肥的袋鼠，袋鼠的体积大于格的行列式。幻灯片上的图像很形象，因为这是个二维空间，我不想把示意图画的太复杂了。图中的袋鼠很肥，它的体积大于格的行列式。如果你仔细看的话，可能会觉得袋鼠的体积还是有点小，但实际上已经足够大了。现在我们有了一个袋鼠，这个袋鼠就是我们取的集合S。我现在要做的是让这个集合S覆盖整个平面，也就是把这个袋鼠图放在每一个格点上，所以我在另一个格点上也放一个，所有的格点上都放一个。这是个袋鼠动物园了，他们都放置在了格点的相同位置上，只不过根据格点的位置来平移而已。现在我们可以观察一下如何形象地证明这个定理。因为袋鼠很肥，袋鼠的体积大于格的行列式，因此总会有重叠的区域。大家想一想，格的行列式恰好等于每个格点周围预留的空间体积大小。如果所选的集合体积大于这个体积，那就没地方了。你可以很容易证明这个结论，袋鼠和袋鼠之间一定有重叠的区域，所以一定会有重叠区域，空间中没那么大的地方。如果你取一个非常大的空间，你会有一大堆袋鼠，每个的体积都很大，袋鼠就没地方放了。

从图上看的话，你会看到一些重叠区域。比如这个区域，这个区域和上面袋鼠的耳朵…我不太熟悉袋鼠的生理结构…上面这只袋鼠的耳朵和下面这只袋鼠的脚后跟重叠了，所以袋鼠耳朵和脚后跟部分有重叠的区域。我们现在要做的是观察重叠的部分。我们在一个袋鼠的重叠区域中取两个点，比如取这只袋鼠，在耳朵上取一点，再在脚后跟上取一点，画一条线。所有这些区域内…注意到这两个点是在一个袋鼠里面的，在一个集合S里面的，那么这两个点的差所构成的向量就是格中的向量。这是一个格向量，这是因为我们是按照格向量来平移袋鼠的，这是因为我们是按照格向量来平移袋鼠的，所以在上面的群中和中间的群中各取一点，它们的差值也是格点，总会形成这样一个向量。你可以证明这一点，这个向量就是格向量。我们现在讲的是非常基础的结论，只要所取集合的体积大于行列式，这里面一定有两个点，他们的差值是一个格点。这个结论证明了Minkowski定理的90%了，我后面会讲剩下10%怎么证明。

这就是Minkowski定理。这个定理称，取任意一个格Λ，然后再取一个集合S。现在S要满足一定的条件，现在这个集合S不能是一只袋鼠了，它需要是一个凸集合，比如幻灯片上的这个集合，是一个凸集合，而且这个集合必须是关于原点对称的。这意味着如果 在S中，那么 也在S中，这就是关于原点对称的意思，也就是S与-S相同。比如幻灯片上的这个区域就是一个凸集合。定理称，如果S的体积足够大，不仅大于行列式，要大于 乘以行列式，那么集合S中一定包含一个非0格点。我要强调包含一个非0格点，因为0点一定在S中，因为集合S关于0点对称，集合S中一定存在一个非0格点。

这就是Minkowski定理。这是一个很强的结论，它告诉我们在特定体中一定包含一个格点。当然，为了可以完成证明，所取区域的体积很大，但这个结论依然非常重要。证明方法如下。在证明之前，我可能要解释一下为什么我们要求是一个凸集合。如果集合不是一个凸集合的话，大家可以想象一下，我们可以在格点的空隙中构造一个集合，这个集合不会碰到任何一个格点。集合可以很大，体积可以特别大，但是碰不到任何一个格点。但是在凸集合中，我们就构造不了类似这种奇怪的集合了。我们还要求它是一个0点对称集合。你可以想象一个不是0点对称的凸集合，比如一个很高的三角形，这个三角形的体积也满足条件，但也碰不到整数格点，但体积也可以非常大。所以凸集合是个必要条件，并不是因为我懒，或者是Minkowski很懒。凸集合是证明所需的条件。

下面就是证明过程。第一个思想是取一个集合S，然后缩小2倍。我这里取一个集合S，然后在每个维度上都缩小2倍。我就得到这样一个集合，我们叫它S/2。我们现在有了集合S/2和S，我们首先要注意集合S/2的体积。我们是在n个维度下对S进行缩小，如果每个维度都缩小了2倍，那么体积会缩小 倍，就像我们缩小球体体积一样，因此S/2的体积比Λ的行列式大。根据前一个定理，我们知道在S/2中一定有两个点 和 ，他们的差形成一个向量， 减 ，所形成的向量是一个格点。到这里还没结束，因为我们要在S中找到一个格向量。我们现在只在S/2中找到了2个向量，它们也在S中，且差值为格点，但是我们差不多找到了。我们还需要做下面两步操作，因为 在S/2中，根据定义，2倍 也在S中，所以我们把 乘以2，我们得到 在S中。类似地，我们取 ，乘以2，再取负数。我们可以取负数，因为我们取的集合关于0点对称。因此， 也必然在S中。

我们现在知道 和 都在S中，这有什么好处呢？现在我们可以取平均数，取这两个点的平均数，这个平均数也一定在S中。因为这是一个凸集合，所以我们在这两个点中取一个中点，这个中点正好等于。 的中点，这两个点的中点就是 。我们知道这是一个格点，因为证明的第一部分说明 是一个格点。这就是Minkowski定理的证明方法了。

这个定理在格中怎么用呢？这个定理实际上说明格中有一个短向量，或者至少说明格中有这样一个比较短的向量。我们要用这个定理的一个推论，这就是推论了。取任意一个格Λ，这个推论告诉我们Λ的最短向量，最长不会超过 乘以Λ行列式的1/n次方。如果大家第一眼看到这个推论，可能会觉得Λ行列式的1/n次方很奇怪，但实际上这是很自然的结论。我们可以忘了这个1/n次方，推论上是这么要求的，这只是一个放缩系数而已。假设我们取一个格Λ，然后把它放大10倍，那么所有的参数都会放大10倍，这样等式左边肯定就被放大了10倍。为了能够让等式正确放缩，我们需要等式右边也放大10倍。这就是行列式1/n次方的由来，因为如果我们把格放大了10倍，根据矩阵的性质，格的行列式会被放大 倍，所以我们要取1/n次方，这样等式左右两边放大的倍数就一样了，等式两边都放大了10倍，这是我们希望得到的结论。所以对格放缩和对矩阵放缩是一样的，没什么区别。行列式的1/n次方是非常自然的结果，必须要取1/n次方，只是一个放缩系数。比较有趣的是 这部分。这个推论的一个等价论述是，对于任意行列式为1的格，必然包含一个长度不超过的短向量。我们可以把这个常数再优化一点，如果你觉得这个常数还不够好，你可以把这个常数优化的稍微好一点。我们可以把系数优化为C乘以，其中C小于1，但我们不用关心这一点，这个问题就没那么有趣了。

怎么证明这一点呢？这个推论只是前面那个定理的特殊情况。我们取一个半径为的球，注意这个球的体积大于 ，如果你取任意一个行列式为1的格，且球的半径是，体积大于，则球中一定包含一个格点，这个格点的长度一定小于球的半径，小于。根据定义我们可以直接得到，这个向量的长度最多不会超过。为什么半径为的球，球体的体积至少为呢？因为这个球内部包含每一个维度都为 的方盒，这个方盒为 ，为什么？因为任意一个在方盒中点的范数最大不会超过，最大的范数也只能属于一个点，这个点的范数等于。大家可能觉得这个放缩浪费了很多空间，但实际上并没有，球体的体积并不比大多少，我在这里就不详细说明这一点了。本质上，这个阶最多到，或者前面乘以一个常数。

现在我们找格中短向量的方法，都是从数学角度取找，我们不知道如何从算法角度找格的短向量。这也是为何可以基于格构造密码学方案的本质原因。格密码学所依赖的假设是，这些问题是困难问题，我们不知道如何高效地求得格的短向量。如果你仔细想想的话，这个假设很神奇，我们已经讨论了数年了，格问题究竟是不是个困难问题？感觉这个困难问题和Blichfeld定理是冲突的，我们可以利用方盒做很多事情，证明很多定理。但是这个定理没有告诉人们如何得到一个短向量，这个定理只告诉人们存在一个短向量，我们不知道如何高效地得到一个短向量。而得到短向量的困难性，这是密码学所依赖的困难问题。这部分有什么问题吗？很好，我们现在开始讲最后一部分内容。

我们来看看格中的计算问题。这实际上是一个很大的领域，我们的讲座不可能涉及到所有的方面，我这里只是希望让大家看一下这个领域发展到了什么地步。后面几天我们要用到这些困难问题，假设这些问题是困难的，基于这些问题构造密码学方案。我们不需要太多关注困难问题本身，Vadim的讲座会稍微详细讲一下这些困难问题，我在周三的时候也会讲到，但我认为绝大多数讲座不会过多讲解这些问题本身。

我们来看看要使用的主要问题吧。首先，我们来看看一些比较简单的问题。首先，这是一个简单的格问题。如果给你一个基和一个向量v，你可以验证v是否在格L(B)中吗？我们如何验证？如何解决这个问题？我们可以用高斯消元法，很好。我们可以用高斯消元法解决这个问题。取这个向量，这里我给定的向量是v，然后把这个向量表示成基向量 的线性组合形式。这种表示方法是唯一的，可以用高斯消元法得到这种表示， 是线性无关向量，只用最基本的线性代数就能做到。然后我们要做的是检查系数是否均为整数，如果系数是整数，v就是格点，如果系数不是整数，v就不是格点，这很容易验证。在后面的讲座中我们还会用到这个算法，这个算法很有用，记住它。这个问题之所以简单，因为它不是一个几何问题。它是线性代数问题，并不是一个几何问题，所以这个问题比较简单。

与之类似的一个线性代数问题是，如果我给定你两个基 和 ，你能否判定，是否这两个基生成的格是同一个格？我们有很多方法可以解决这个问题。第一种方法是用我们前面得到的一个结论来解决。我讲过，两个基是等价的和是等价的，当且仅当等于乘以，其中是一个幺模矩阵。所以你可以试着求一下 ，计算 乘以 的逆，你会得到一个矩阵，检查一下这个矩阵是不是幺模矩阵。可能我们根本不需要用这么复杂的方法解决这个问题，还有另一种更简单、更基本的方法来解决这个问题。这种方法是，取基中的任意一个元素，任意一个向量。对于每一个向量，检查这个向量是否属于另一个格。一共可以取n个基向量。对于每一个基向量，检查这个向量是否属于另一个格。如果每一个基向量都属于另一个格，你会得到 包含于 中，因为如果基向量元素在 中，意味着基向量的全部整数组合也在 中，因为格对于加法是封闭的。我们反过来再检查一遍，取 中的每一个基向量元素，检查每一个基向量元素是否在 中。如果这也满足的话，你就得到这两个基是等价的，因为第一个格属于第二个格，而第二个格又属于第一个格，所以这两个格等价。还有很多方法可以解决这个问题，这两种解决方法都很简单。

我们现在开始讲一个比较困难的问题。一旦格问题是一个几何问题，比如讨论长向量、短向量什么的，那么这个问题就会变得很难，比想象中要难得多。这是一类典型的格问题，这个问题叫做最短向量问题。这个问题是，给定一个格，我的意思是指定一个格，大家需要理解一下何为给定一个格，这很重要。我们一般用一个基来描述格，我指定格中任意一个基，这个基可能不是一个好基，基可能包含非常长的向量。现在我的问题是，你能否在这个格中找到一个短向量？你能找到 的一个整数组合，使得各个系数能够互相消除，所得到的向量成为一个短向量？这就是最短向量问题，我们在密码学中常用的困难问题是它的一个变形，也就是近似最短向量问题。这里有个参数γ，γ是一个近似因子，我要求你找到一个向量，这个向量可能不是最短向量，只要小于最短向量长度的γ倍就可以。这就是 问题，找到一个向量，这个向量的长度小于最短向量长度的γ倍，也就是γ乘以 。在后面几页幻灯片中，我会讲到这个问题的当前研究进展，这是一个典型格困难问题。

我需要指出的是，这个问题还有很多变种。这个格问题要求得到这个短向量，我们已经理解这个问题了。这个问题还有一个变种，这个变种问题像是一个判定性问题，是一个间隔问题。我现在不让你找到这个向量，你只需要告诉我这个向量的长度是多少，我要求你告诉我近似最短向量的长度是多少。举例来说，我要求你告诉我，近似最短向量的长度小于1，还是大于γ？我不会讲过多细节性的内容，大家只需要知道，这个判定性问题在密码学中起到了重要的作用，大多数密码学构造是基于这个问题或下面这个SIVP问题的。再强调一下，SVP和GapSVP这两个问题，都涉及到一个近似因子γ，这是一个非常重要的参数。随着γ的变化，这个问题会变得更难或者更简单。当γ很大时，这个问题会很简单，因为我们不要求向量长度很短了。但是当γ很小时，这个问题就会变得非常困难。我在后面几页幻灯片中会详细讲解γ的取值范围。

我们再来讲几个格困难问题，这个问题在密码学中很重要，因为很多密码学构造，大多数密码学方案构造都依赖于这个问题。这个问题叫做最短独立向量问题。这个问题涉及到的参数是 ，和SVP问题有些类似。SVP问题让你求得最短向量，或者求得γ倍的最短向量。SIVP问题中，我要求你找到格中的n个线性无关向量，并且要求这些线性无关向量的长度，不能比最短线性无关向量长太多。最短线性无关向量最长范数为 ，这是由定义得来的。根据定义，我们能得到的最短线性无关向量最长范数为 ，这是n个线性无关向量所能得到的最短范数值。现在我让你找n个线性无关向量，他们的长度最多不能超过 的γ倍。举个例子，我们有这两个基向量 和 ，它们生成了一个特定的格，我们不知道它们产生的格是个什么样子，很难从计算的角度指出产生的格是个什么样子。在这种情况下，我要求找到两个短向量。这实际上是最短向量，这实际上就是 ，不过一般情况下，我们只要找到两个近似 长度的向量就可以了。

你可能看到过其他一些格问题，我们在周二会讲到这个问题的一个等价定义，所以我们不用记用这个方法定义的问题。不过这个问题很自然，叫做最近向量问题。最近向量问题是指，我们有一个格，我们有一个点v，我让你找离点v最近的格点。有多近呢？不一定要特别近，距离比系数γ倍小就可以。这个问题叫做最近向量问题。我们有一个点，试着找一个离这个点比较近的格点，不一定离得很近，和最近点的距离小于一个系数倍数就行。这就是CVP问题，最近向量问题。

这两个问题实际有一定的关系，这是一个很好的习题。这个关系是由Goldreich、Micciancio、Sofra和Seifert在1999年发现的，这个关系可作为一个很不错的习题。其实有很多类似这样的困难问题关系，但是这个结论更好，这是格困难问题中的一个经典结论。这个结论指出，对于任意近似因子γ，SVP问题不比CVP问题难。换句话说，如果你有方法，能在近似因子等于10的条件下解决CVP问题，那么你也可以在近似因子等于10的条件写解决最短向量问题。如果在二维空间下考虑这个问题的话，这个结论挺直观的。我们可以怎么解决这个问题？0点。我想找到一个短向量，我应该怎么做？我可以让CVP问题帮我找一个离0点最近的向量，希望能找到这样一个短向量。但问题在于我得到的也会是0向量，因为0是与0最近的向量，这个结果没什么用处，因为我们实际上要寻找的是最短非0向量。这里面涉及到一个很聪明的技巧，你可以试着想想这个技巧是什么。你可以尝试修改归约算法，比如向CVP问题问询一个不是格点的点，或者取一个子格，问点与子格点距离比较近的点。这需要一些证明技巧，这个证明很漂亮，你可以思考一下如何证明，这很重要。

最后我给大家讲解一些直观结论，这些问题互相之间都有一定的联系。这些问题有强烈的互相关性，虽然学者们还没有证明其中的一些相互关系。第一个与之相关的问题是定距离编码问题，或称BDD问题，这就是定距离编码问题。这个问题与CVP问题类似，即与最近向量问题类似。我现在告诉你，点v是一个与格点很近的点了，现在你需要精确解决这个问题。你已经有了一个与格点很近的点了，你需要找到这个最近的点。这个问题在格密码学中占有重要的地位。这就是BDD问题，定距离编码问题。

针对这些问题，我们已经知道了很多结论。当然，我不会详细讲解证明过程。我希望大家能够明白格的历史进程，以及为什么我们认为格对密码学来说非常重要。你可能觉得，这些问题不应该这么难啊？但实际上，学者们已经深入研究了这些问题。从算法角度我们得到了哪些结论呢？学者们一直在尝试提出算法来解决格困难问题。我们学到的第一个算法1982年提出的LLL算法，我最后会告诉大家这个算法是怎么回事。这个算法是一个多项式复杂度算法，是一个高效的算法。你可以运行一下这个算法，现在已经有很多现成的软件包支持这个算法了。这个算法可以在高维空间中运行，比如几百维空间中运行，运行起来也很容易。这个算法能输出什么呢？能输出一个短向量。这个算法的问题在于，输出的短向量只是比较短，更准确的说，近似因子接近为 ，所得到的向量比最短向量要大 倍，大的倍数是指数级的。即便这样，算法构造也不那么直观，特别是当n很小时，如果我们在低维度环境下运行这个算法，这个算法实际上一般也在低维度下使用。在密码学攻击算法中，所涉及到的维度n都比较小。当n比较小时，你可以用这个算法做很神奇的事情。但是在高维空间下，在密码学中使用这个算法时，比如维度等于500时，很重要的一个结论是，这个算法输出的结果非常差，会输出一个非常长的向量。 是一个指数近似因子，是一个很糟糕的近似因子。这是Lenstra、Lenstra、Lovasz提出的算法，Schnorr、Ajtai、Kumar、Sivakumar提高了算法的性能。

最近学者也提出了另一个工作路线。这个路线很有趣，这个路线从另一个角度破解密码学方案。这个路线是找到一个算法，这个算法确实可以解决最短向量问题，但学者们要做的工作是提高算法的性能。这个工作很有意思，算法的复杂度不再是多项式级的了。我们已知的最好的算法复杂度是 ，需要指数级的运算时间。这个领域还有很多有趣的工作。这个工作是2002年由Ajtai、Kuma、Sivakumar开创的，最近Micciancio、Voulgaris也得到了一些这方面的结论，Gama和Nguyen这几年也提出了新的结论。我们已经得到了很多有关解决格困难问题的结论，里面有很多有趣的想法。有些想法是用体积比较大的几何体来证明，如前面我讲到的一些定理证明思想，比如用一个椭球体，很多很有趣的想法。但是现在学者们还没找到算法 能在小于 复杂度下解决格困难问题，似乎很难把算法复杂度优化到 以下，这让密码学家们相信，与格相关的困难问题确实很难。

正如我前面提到的一样，与整数分解问题相比，格困难问题可能更好一些。你会看到，针对整数分解问题我们已经得到了一些比较好的算法。刚开始的整数分解算法很慢，需要指数时间复杂度。现在学者们得到了亚指数复杂度等更快速的整数分解算法。这些算法的效率非常高，都是亚指数复杂度算法。在人们提出整数分解问题时，人们都没想到能找到这么高效的算法。

与整数分解相比，再看看近30年来格困难问题的发展情况。学者们也提出了很多好的想法，提出了很多漂亮的算法，但是如果从性能提升的角度思考的话，并没有什么过多的进展，仍然需要 时间来解决这些困难问题。这是一个积极的信号，告诉学者们这些问题确实很困难。可能如整数分解问题一样，我们还可以提出更高效的格问题算法。至少从数论角度上来说，人们已经提出了很多令人惊讶的算法，但并没有任何证据证明算法性能不能进一步提高。性能总是还可以再提高的。

另一个比较好的特性是，同样与整数分解问题相比，比较好的特性是，学者们也没找到量子算法。如果你从量子算法的角度思考这个问题，你会发现即使从量子算法的角度考虑，学者们也没提出比较好的算法，所以可能格困难问题确实很困难。

这个数轴上有两个区域。我们一直在讨论的是近似因子为指数的右边这个区域，当近似因子大于 时的这个区域。另一边是NP困难区域，我们认为这些问题是NP困难的，这里涉及到的近似因子很小。密码学上这边区域的假设没什么太大的用途。我希望大家了解到的是，如果γ非常小，比如小于n的一系列log(n)次方什么的，我们得到的是NP困难问题。这些就是GapCVP问题了，Villas Boas在80年代早期提出了这个问题，Dinur、Kindler、Raz和Safra得到了有关这个问题的更强结论。对于SVP问题，也得到了类似的结论。这些结论表明，这些问题的困难度非常高。这里我们可以看到一个小区域，这里近似因子小于多项式级，但是比常数近似因子好一些。这些问题是NP困难的，但是密码学上我们不过多关注这个区域内的困难问题。

密码学上关注的区域是…Vadim会在下面的讲座中讲到，这个区域差不多是从这个近似因子开始的。近似因子等于n或者大于n，密码学关注近似因子γ落在这个区域的困难问题，比如近似因子等于n，或者等于n的1.5次方，基于这个区域的困难问题。Ajtai和其他一些人，基于格问题构造了单向函数。我们也构造出了公钥密码学方案。在冬令营后面的讲座中，大家可以学习到，密码学所依赖的困难问题，近似因子落在n到n平方之间，也就是落在多项式近似因子上，近似因子是n，我们并不适用NP困难的区域。

学者们也在另一边得到了很棒的结论，我们称其为不可近似受限性。这方面的结论称，这些困难问题不像是NP困难问题。它们指出，当近似因子大于根号n后，在近似因子落在根号n的右边时，这些问题是NP和coNP之间困难的。因为这些困难问题落在NP和coNP之间，所以他们应该不是NP困难问题。这实际上告诉我们，我们所设计加密系统的安全性是基于困难问题的，但是我们不能期望基于NP困难问题来构建密码学方案，因为NP困难问题有很多限制条件。这里我稍微讲一下为什么我们相信这些问题是困难的。基于NP困难问题构建密码学方案应该很难做到，但这已经超出我们讲座的内容了，但我们可以证明的是，我们发现这些问题不是NP困难问题，因为我们可以证明这些问题是NP和coNP之间困难的。

我们最后总结一下接下来几天我们要讲的内容。我们关心的问题是近似最短向量问题、SVP或者SIVP问题，其中近似因子为n或者n的1/3次方，或者n的平方。我们认为这些问题是困难的，已知可以解决这些问题的最好算法需要指数级时间 ，时间与维度成2次指数关系。不仅是解决原始困难问题，对于近似因子为n或者n平方的困难问题，最好的算法也就是这样的。我们没有找到更好的算法，并且我们没有找到量子算法，所以这些问题很困难，即使在量子算法条件下也很困难。另一方面，我们认为其中一些问题是NP困难的，这些问题似乎没有什么好的应用价值，我们只是认为这些问题非常困难，我们基于这些问题构造密码学方案。

现在轮到Vadim上台了，我们明天应该还能，再给大家做一个讲座，非常感谢。