2012年BIU密码学冬令营-02-SIS归约-第1部分

演讲视频简介

Oded Regev的第一个视频终于是更新完了。我们继续带来2012年BIU密码学冬令营Lecture 02的讲座，Vadim Lyubashevsky讲解SIS归约问题。与Oded Regev的讲座相比，我个人认为Vadim Lyubashevsky的讲座听起来会更轻松一些。不过Vadim Lyubashevsky讲座中的口头语特别多，这导致字幕显示得比较凌乱，效果不佳。建议对这部分内容感兴趣的知友直接看我在B站上传的视频。当然了，知乎专栏的好处在于公式显示会比较清晰。

不得不说，整理视频字幕是一个很爆肝的事情。无论纠正多少轮，还是能发现字幕中的错别字、翻译不对的地方等。这方面还望知友们多包涵，一遍一遍地更新和重新上传更痛苦…

Lecture 02第一部分的内容主要包括两个内容：（1）用格构造抗碰撞哈希函数；（2）高斯分布在格中的作用。

演讲视频信息

演讲视频字幕

好了，我们继续吧。首先，感谢Yehuda给我这样一个与大家分享的机会，同时感谢Claudio提醒我把幻灯片发过来 ，要不然我就讲不了了… 抱歉把你的邮件给无视了。

我们继续往下讲…这个讲座分为两个部分，后面的部分将在午饭后讲解。后面的部分将讲解一个重要的结论，这个结论开创了格密码学的先河。这个结论首先是由Ajtai提出的，Micciancio和Regev完善了这个结论。但是在午饭前的一个小时，我需要为大家讲解一些数学工具。后面讲到的结论中要用到这些数学工具，格密码学后面的一些内容也要用到这些工具。这些工具都非常有用，研究者们后来指出格中到底需要什么样的工具。至少到现在为止，这些工具完美迎合了格的需求。当你发现格中的一些性质，而且这些性质看起来是正确的，但是为了证明这些性质，你需要一些数学工具，而这些工具本身就非常惊艳。

我今天演讲的大纲是，首先，我要给出这些平均困难问题。你可能已经听过最糟糕困难归约、平均困难归约这些词语了。这里所说的平均困难也是困难问题。我要先讲解平均困难问题，叫做Small Integer Solution问题，是一个格中的根本问题。接下来，如果你已经看过不少论文的话，你会看到“高斯分布”这个词。高斯分布是最常见的一种概率分布，生活中很多地方都会用到。但是这个分布在格中具有非常重要、非常特殊的意义。高斯分布与格可以说是完美契合。我也会讲讲高斯分布以及它和格的关系。我会讲到，也希望大家能够理解到，为什么这个分布是格中最重要、最正确的概率分布，为什么在格里面用这个概率分布才是正确的。后面的讲座中，我们每天都会用到高斯分布，Chris在他的演讲中也会用到高斯分布，明天的每个讲座中都会用到高斯分布。在证明困难性时，星期三的时候，Oded的讲座中也会用到高斯分布。这个分布将会一直伴随着大家，所以我认为有必要深刻理解，什么是高斯分布，为什么高斯分布如此重要。在午饭后，我会讲一讲最糟糕困难归约。实际上，一旦你有了这些数学工具，归约算法本身的基本思想是非常直观，非常简单的。

好的，我们先来讲讲平均困难问题。正如Oded提到的，有不少密码学算法是建立在格中最糟糕困难问题上的。但实际上，我们并不是只能在格中最糟糕困难问题上构造密码学算法。学者们提出了一些平均困难问题，比如SIS问题、Learning With Errors问题。我们所要做的是，如果某人想基于最糟糕困难问题构造密码学算法，这个人只需要考虑这两个问题。可以考虑SIS问题，有很多不同类型的SIS问题，可以根据算法构造选择使用哪个类型的SIS问题。如果基于SIS问题，似乎只能构造minicrypt Minicrypt这个词。如果你年级不大的话，这是Impagliazzo提出的计算机科学5层世界之一。你可以在Minicrypt层派生出单项哈希函数，或者随机预言。随机预言是更一般性的minicrypt。这一层有单项哈希函数、抗碰撞哈希函数、数字签名、ID方案，差不多就这些密码学方案。但这一层已经包含了密码学中最重要的原语了，就是数字签名。这一层很有用。另一方面，我在这个讲座中不会涉及到另一边的假设，Chris在下一个讲座中将讲到另一边的假设。另一边是Learning With Errors假设。在这一边，你可以得到公钥密码学，以及与公钥密码学相关的密码学方案。我们明天会看到更多这样的方案。

如果我们把最糟糕困难问题拆开，里面有两个格问题。第一个重要的格问题是SIVP问题，全称是Shortest Independent Vector Problem。另一个重要的格问题是BDD问题，就是Bounded Distance Decoding。这两个困难问题非常重要。正如我近几年所指出的，这是格中的两个重要问题。这两个问题之间还有内在的联系，如果你可以解决SIVP问题，你就可以解决BDD问题。如果你可以解决BDD问题，你可以在量子计算机下解决SIVP问题。我不会详细讲这两个困难问题，这不是我们讲座的主要内容，大家只需要知道有这么两个困难问题。

我们来讲一讲最重要的一个问题，即Small Integer Solution问题。这就是SIS问题了。第一眼看过去，这个问题好像和格没什么关系。实际上，如果某人想基于这个问题构造密码学方案的话，这个人甚至根本不需要了解格的相关知识。但如果不了解格知识的话，可能你也没法深刻理解所构造方案的安全性，因为格会帮助你理解为何所构造的方案是安全的，安全性从何而来。

这就是SIS问题了。SIS问题是，给定m个在 中的向量，这些向量都是随机选取的。随机分布在这里起到了重要的作用，如果你想基于大整数分解问题构造算法，你需要选取大整数N，那么如何选取大整数N是个很重要的问题。你是随机选取P和Q，还是用其他什么方法选？但这里，我们只需要随机选取向量就可以了。随机选取的Small Integer Solution问题已经是最糟糕问题了。在 中随机选取 。SIS问题是，在 中找到非平凡的 ，也就是说 只能从 中选，使得幻灯片图片上公式的和为0。

为什么我要强调非平凡解呢？0，是的，你可以把所有的 全都设成0，0是一个平凡解。我们不需要平凡解，我们需要其他的解。我们来观察一下这个问题。如果不限定 范围，也就是说，如果 可以不仅从 中选，这个问题就比较简单了。怎么解决这个问题？好像有个人一直在举手示意，在这儿呢。怎么解决这个问题？高斯消元法。如果不限定 的范围，那么这个问题非常简单。限定 的范围是非常重要的。在下面几页幻灯片中我会讲到，估计大家现在已经猜到了，如果这个问题是困难的，你马上可以基于SIS问题构造抗碰撞哈希函数。我用后面两页幻灯片就能讲明白，构造非常直观。

有趣的是，即使第一眼看上去，这个问题好像和格没什么关系。实际上这个问题与格的关系非常密切。这就是SIS问题与格的关系了。SIS问题要找到一个非平凡解，使得这个线性等式值为0。但如果仔细想想的话，就会发现非平凡解所构成的集合形成了一个格。令S表示所有整数组成的集合，这里没有限定范围， 的和在模q下等于0。所以很明显，对于任意两个解，这两个解的和也满足模q等于0，所以解的集合构成了格。所以SIS问题实际上要得到的是，找到一个满足一定范数要求的短向量，这里我们限定了 ，所以无穷大范数是1。如果我们取 范数，困难性是等价的，即找到S中的一个短向量。

我们有两种方法表示一个格。第一种方法是使用格的基，我们可以把基向量写成列向量的形式，用构成的矩阵表示格。这里的x表示基的整数组合，所有这些就都构成了格点。另一种方法是用矩阵A，你可以把这些列向量想成前面黄色框中的 ，然后要求这些 的线性组合等于0，这些也是格点。这个格是个高维格，维度为m，左边的格维度为n，右边的格维度为m。这里好像被截断了，没关系。所以平均困难到最糟糕困难的归约指出，如果你可以解决SIS问题，你也可以解决格中的最糟糕困难问题。但是如果用格的说法来解释的话，你可以说，如果你可以在这些随机格中找到一个短向量，你就可以在所有的格中找到一个短向量。本质上，并不是所有的格都可以写成右边这种形式，但是在这些格中寻找短向量的困难程度，与在任意其他格中寻找短向量的困难程度是一样的，因为任意格斗可以表示成左边这种形式。注意到这两个格的维度不太一样，右边的格维度是m，左边的格维度是n。这里我可以回答你刚才提的问题了，m近似等于 。

关于SIS和格关系，我就讲这么多。这些内容和后面要讲的归约算法关系不大，我只是希望给大家讲一下思路。 SIS问题和格之间关系的基本思想就是这样。SIS问题并不是凭空而来的，它与格的关系非常密切。

好的，我们来看看这个图，我们要讲的是红色的部分。我们首先讲一讲，如何基于SIS问题构造抗碰撞哈希函数。如果你可以破解哈希函数，你就可以解决SIS问题。

我们先来复习一下什么是抗碰撞哈希函数。可能大家对这个概念没什么印象，就好像Oded对美国没什么印象一样。我们有一个哈希函数族H。这里面的所有函数都有定义域和值域。对于H中的任意一个随机的哈希函数，很难在定义域中找到两个元素 和 ，使得他们在值域中的值是一样的，这需要是一个困难问题。这就是抗碰撞哈希函数。

我们基于SIS问题来构造这样一个哈希函数。我们有SIS问题，我们这样定义一个随机哈希函数：随机选择 ，这些 就是哈希函数所需要的全部参数了。具体怎么计算哈希值呢？哈希函数的输入是一个各项在 中的向量z。这也可以回答Daniel的问题，无穷大范数有时候很有用。这里用 范数就没那么方便了。我现在要映射比特值，我得先把比特值变小，拆成一位一位的，这个时候自然而然要用到无穷大范数。h的输入是 ，然后你只需要做加法。h的定义域是 。抱歉，取值范围并不是 ，就是 ，所有这些都从 中取值。h的定义域是 ，也就是说，定义域的大小是 ，值域是 ，值域的大小是 。Chris让我好好讲讲这里，如果你确实想知道刚才问题的答案，这里是q与n关系的来源了。如果这是一个抗碰撞哈希函数的话，我们需要让 大于 。这是个哈希函数，所以我们要设定m大于 。

现在假设你可以找到一个碰撞，也就是说你可以破解这个哈希函数，那么你可以找到某个 ，其结果等于 ，这样才算你破解了这个哈希函数，所以SIS问题也解决了，对吗？ 只需要做减法，得到 ，并且 的范围都是 ，很直观，不需要什么推导过程，对吗？所以很明显，通过SIS问题可以直接得到一个抗碰撞哈希函数。没有人要提问？很好。

现在，我们来讲下一个有趣的部分。我们要从Small Integer Solution转移到SIVP问题上。这里我需要提醒一下，抗碰撞哈希函数的构造非常简单直观，但是其他密码学方案的构造就不那么直观了。基于格的密码学方案构造还有很多工作等着我们去做。但在这一周内，我不会讲解相关构造的。不过这些方案构造也不是很多。

好的，我们先来讲讲这部分，这部分很有趣。但在讲这部分之前 我们先要讲讲高斯分布。

这是一个一维高斯分布，一般用ρ来表示。这里有个参数s，表示高斯分布的标准差。一维高斯分布定义为 。我们来看看高斯分布的意义是什么，看看用高斯分布能得到什么。我们先忽略这些项，这些项是用来缩放的参数，使它成为一个概率分布，因为概率分布的全域积分应该等于1。我们来看一下，随着x的增大，x对应的概率减小。也就是说，离原点越远的数，所对应的概率值越低。随着s的增大，每个x所对应的概率值会变大，这就是标准差的意义，如果s的取值非常大，那么函数会变得更平滑。

这是一个正态分布，这是最经典的正态分布，概率分布依0中心对称，且标准差为 。有的人表示正态分布时直接把标准差写为s，这个有历史遗留问题，现在人们常用这种表示，所以我这里也用这种方法表示高斯分布。

这是个高斯分布的例子。这是 时的高斯分布，可能大家看不到坐标轴上的数字，再往后x对应的概率就变得特别小了。这里需要很多数学知识，基本上都是数学知识。黑色区域是 时的高斯分布，阴影区域是 时的高斯分布，当s的取值变大时，概率分布变得更加平滑了。这个图不太清楚，但我们不关心一维高斯分布，对于格来说，我们一般讨论高维格，我们关注的是n维高斯分布，多维高斯分布。

高斯分布有一个很棒的特性，你可以利用一维高斯分布来构造高维高斯分布。这是二维高斯分布，二维概率分布中，点(x,y)取值的概率分布是什么？首先我们在第一个轴上，在 轴上做一维高斯分布， ，这是一维高斯分布。在另一个轴上也做同样的一维高斯分布，只不过我们在一个垂直的轴上做分布。我们就把 换成 ，就得到了这个分布。现在点取值的概率分布是什么？也就是说一个点在两个轴上的联合概率分布是什么？就是它们的乘积。这是个概率分布，也就是在这个轴上取值的概率，和在另一个轴上取值的概率，所以我们把这两个概率乘在一起，很简单，乘起来就好了。

我们现在还没用到高斯分布的任何特性，你做乘积，指数上的项会相加，我们会得到一个很有趣的结果。你得到的是 。这个结果很棒，因为指数上只是x的范数，也就是x与原点的距离值。这意味着，取得点x的概率只与点到原点的距离有关。很好，没什么问题。

这是一个二维高斯分布的例子，这个图好像是从维基百科上拽下来的。你们能看到图的颜色吗？不行…蓝色代表低概率，红色代表高概率，所以这个概率分布有点像个山峰，这个图挺不错的，这就是二维高斯分布。

我们可以类似定义n维高斯分布，所以取得向量x的概率是 。这就是n维高斯分布，这个分布仍然依0点对称，标准差是 。

我们来看看这个标准差，这个标准差的主要作用是什么呢？如果你有一个一维高斯分布，如果依一维高斯分布取点，那么取得的点到原点距离的期望是多少？也就是说，如果你按照一维高斯分布随机取一个点，这个点到原点的期望距离是多少？是比标准差大，还是比标准差小？距离期望的平方是多少？方差，正确，距离的平方就等于方差，也就是标准差的平方，所以距离小于标准差，小于根号下方差，但是不会小太多。所以标准差在这里非常重要，因为它可以告诉你所取点到原点的距离大概是多少。在n维高斯分布中，如果标准差是这个值的话，那么所取点到原点的距离大概应该是多少？在每一个维度，距离都是这个，所以在n维，距离是根号n乘以这个值。这非常重要，如果你按照n维高斯分布取点，所取点到原点的距离近似为这个值。我这里用了近似这个词，因为距离的平方是方差，但是距离本身可能不是方差开根号，并不完全是，但是很接近，距离与标准差会非常接近。

高斯分布有很多有用的性质。一共有三个性质，前两个性质其实在前面的讲解中或多或少已经提到了。第三个性质是最有趣的一个性质，我认为是最酷的性质，而且这个性质在格中具有重要的意义。我们先来看看前两个没什么意思的性质，然后来看看第三个性质。

首先，这是一个乘法概率分布，这意味着你可以把概率分布写成一维概率分布相乘的形式。我们已经看到二维时的乘法特性了，n维情况也是一样的。

其次，这是一个球对称概率分布。这意味着x的概率分布只与x到原点的距离有关，也就意味着我们不用考虑如何选择轴，我可以横平竖直的选择轴，我也可以斜着选，这都没关系，x的概率还是一样的。我可以根据我需要的情况任意取轴，但是不管怎么取，概率分布还是一样。另一方面，知道概率分布后，你也不知道我是怎么取的轴，只知道这些轴是相互垂直的。从这个图片中你无法得知有关轴的任何信息，轴可能是横平竖直的，也可能是斜着的，所以概率分布是球对称的，这很有用。

现在我们来讲最重要的性质，在线段上产生满足均匀分布的元素，我们有这样一个性质。现在我们回到一维高斯分布，我们有一个一维高斯分布，我把与标准差相关的s设置为M的5倍大小。M是某个值，比如M为1。第三个性质是这样一个定理，如果X是依高斯分布取值的，那么对于所有的 ，从统计距离上看， 的分布非常接近于 的均匀分布，两个分布的统计距离差值小于 。可能大家不知道这个性质，但这个性质太令人惊讶了。

我们来试一试，假设我让你产生一个点，这个点的概率分布在模10下是均匀随机的，你会怎么做？你估计会说，这很容易，我就直接在模10下产生一个点，没什么问题。接下来我会说，我想让你产生一个点，这个点的概率分布在模10和模9下都是均匀随机的。这时你就不能先产生一个模10下均匀随机的点，然后再把它模… 因为模10下如果是均匀的，没问题，你满足了我的第一个要求。但是第二个要求是，同样一个点的取值在模9下也是均匀随机的。第二个要求就不满足了，因为如果你在模10下均匀随机地取一个点，当你在对这个点模9，那么 区间所在的部分概率分布就要大了，所以怎么办呢？你会说，好，我在模90下产生一个均匀随机的点。很好，这也没问题。现在我说，如果我想得到一个模10、模9、模8都均匀随机的点呢？现在模9是均匀随机的，但是9不是8的倍数，所以模90均匀随机只能保证模10和模9均匀随机，但是模8下做不到均匀随机，怎么办呢？你可能能猜到我接下来的要求了，我让你产生一个模10、模9、模8下都均匀随机的点，或者模5.5、模6.1的。对模的值甚至可以没什么要求，我想模什么就模什么。如果某人想在某个概率分布下产生一个点，要求这个点模掉任意小于10的数都是均匀随机的，怎么办？我的意思是这个线段得取多长？我们可以把被模数都乘起来，但是这只对整数有效，如果我希望模掉所有的小数后也是均匀随机的呢？我的意思是 唯一的方法是，你不得不产生一个点，在模 下均匀随机地产生一个元素了，因为如果在模 下均匀随机地产生一个点的话，统计距离可以满足条件。但你要做的是，生成一个非常大的点，而目的只是为了让它在模任意小于10的数后是均匀随机的。但是如果你依高斯分布取点的话，你要做的就是，依高斯分布取点，并且把标准差设为5M。这样一来，所取点在模任意小于M的数后，都是均匀随机的。

如果在座的各位知道有关随机行走问题的话，那个问题和这个问题有点像，因为如果你在线段或者圆上进行随机行走过程，并且你想知道我需要走多少步，才能让足迹在路线上是均匀的，那么随机行走的概率分布要满足高斯分布。不过这里我不会讲过多关于高斯分布的内容。

这里有个例子，这个图中 且 。注意如果 的话，就成为均匀分布了，不过现在还不是均匀分布。我们来看看。左边是高斯概率分布的图像，右边是这个高斯分布模1后的概率分布。注意到现在还不是均匀的，很明显能看出来，在边缘上的概率分布值很大，在0.5左右时概率分布值最小。你也可以看出为什么会这样，因为把这里模1的话，边缘部分的概率值就变大了。同时，负数部分也会比较大，负数部分与0附近的概率值相关，正数部分与1附近的概率值相关，但在0.5附近，概率值就比较小了。我的意思是，中间的部分得不到太高的权重比，所以右边的图像才会是这个样子。

我们来看看当 等等时的结果。我前面讲到过这个例子，图像会变得越来越平滑。这是同样一个高斯分布模0.9后的结果，可以看到，这还不是均匀分布，我们现在还得不到均匀分布，大家还看不到均匀分布现象，现在还不是均匀的。但是与之前相比，图像变得更平滑了。这个图是 的情况，变得更平滑了，所以这确实有效。这么一个神奇的概率分布竟然能做到这样的事情。现在 ，从图像上看概率分布是均匀的了，但如果你仔细看坐标的话，这里是0.9999995，这里是1.0000005，所以你仍然可以看出，这还不是统计近似的，但是和均匀分布已经非常接近了，这就是统计近似的了。实际上，这里 ，还不是 的情况。我们在 下也做了实验，结果是一样的。这就是高斯分布在一维下的一个神奇的性质，我们已经讲了很多了。

但我们关心的是并不是一维情况，我们关心的是n维情况。现在我们知道高斯分布模一个区间后的结果了，在n维下会发生什么呢？我们真正关心的是模一个n维平行多面体的结果。正如Oded前面提到的，这是模一个平行多面体后的样子。我们假设模的平行多面体是这样的。这是第一个向量，这是第二个向量，你要做的是，任意选择一个点，然后把这个点表示成第一个向量乘以某个小于1的数，加上第二个向量乘以某个小于1的数。你要做的是，不断从这个点开始，加上或者减去格点，让它最终落到平行多面体里面，这个点也是一样的，能做到吗？这与这个点是等价的，这与这个点是等价的。我们想产生一个点，利用高斯分布或者其它分布产生一个点，使得这个点模平行多面体后在空间上是均匀随机分布的。所以现在的问题是，我们知道在一维空间我们应该怎么做，在一维空间上，你选择一个与参数s相关的标准差，使得标准差为5乘以M，其中M是线段的最大长度。但是在平行多面体下我们应该怎么做？常数s应该选多大？我们应该把s设置到多大，才能保证点在平行多面体内是均匀随机的？这是我们现在要解决的问题。这个问题的解决对于最糟糕困难到平均困难问题归约来说非常重要。

我们先来看看简单的情况。假设我们并不模一个平行多面体，而是模一个方盒，大家认为s应该取多大？如果我们假设，每个方向上方盒的长度都不会超过m，s应该设置为多大？m的平方？为什么方盒时要设置为m的平方？不对，这是一个n维方盒，所以你认为应该设置为 ？并不是 ，和前面一样，应该设置为5乘以 的最大值，为什么？假设方盒B每个维度上的长度分别为 ，并且所有的 都小于M，如果你依高斯分布生成各维度的 ，且s等于5M，我们知道在每一个维度上，如果我们只看一维高斯分布的话，每个维度模 都是均匀随机的，这里写的是模 。所以对于任意一个j，随机变量的统计距离都与均匀分布的统计距离相似。如果每个维度都是统计相似的，那么在方盒中也会是统计相似的，所以方盒的情况非常简单。对于方盒的情况有什么问题吗？

如果是个旋转后的方盒呢？但这是个乘法分布，还记得吗？应该是性质一。我们可以沿每一个维度依概率独立生成此维度的坐标，从而生成方盒中的点。如果是旋转后的方盒呢？如何生成一个点，使得它模这个方盒后，是均匀随机的呢？旋转轴不会影响概率分布，因为概率分布是球对称的，这用到了另一个高斯分布的性质，概率分布与轴的选取无关，所以旋转后的方盒和方盒本身是一样的。

现在我们来看最原始的，也是最有趣的问题，如果是个斜着的盒子呢？假设我们有一个方盒A ，以及一个跟A没什么关系的方盒B。现在的问题是，已知X模A是均匀随机的，我们想知道X模B是不是均匀随机的？B需要满足什么条件？B和A要满足什么关系，我们才能确定，如果X模A是均匀随机的，那么X模B也是均匀随机的？

可能我们脑海中会首先想到一点。你可能会说，如果B的体积远远大于A的体积，意味着B的行列式远远大于A的行列式，那么可能结论不成立。可以考虑这么一种情况，模A下是均匀随机的，但是B的体积远远大于A，则模B下就不均匀随机了，这很显然，所以有可能B的行列式不能比A的行列式大。

我们进一步假设B的行列式等于A的行列式，左边是A，右边是B，A的行列式确实等于B的行列式。但是这种情况下好像也不行，因为虽然模A下是均匀随机的，但B在水平方向上距离很长，所以模B下也不是均匀随机的，超过A区域的B区域估计就没有概率分布了。

好的，有两种情况下，上述结论是成立的，如果某个分布模A下均匀随机，则这个分布模B下也均匀随机。令B等于A乘以U，其中U是一个矩阵，行列式为1，这意味着B的行列式等于A的行列式。所以如果下述情况之一成立，则如果X模A是均匀随机的，那么X模B也是均匀随机的。这并不是所有的情况，我的意思是有些其它情况下结论也成立。

如果U是一个整数矩阵，则结论成立。U是一个整数矩阵意味着什么？B和A是什么关系？B和A是同一个格的基。如果U是一个整数矩阵，那么这两个格是一样的，B和A生成同样的格。那么如果X模B是均匀随机的，则U模A也是均匀随机的。

另一种情况是，如果U是一个上三角矩阵，且对角线上全为1。在座的各位可能一眼看不出来这个矩阵有什么特殊性，但其实在前面的讲座中你见过这个矩阵，这种情况下结论也成立。

我们首先证明第一个定理。在证明之前，我们先来做一些简单的假设。我们本来不应该在实数上考虑问题的，不过现在先假设，我们把实数域分割成了非常规则的网格。这些网格都很小，并且任意两个平行多面体的行列式都相等，意味着网格的体积都一样，那么网格中点的数量就是一样的。这个结论严格来说只在无穷大上成立，我这里先做个假设，假设这是成立的。这样我们就可以构造一个一对一映射。我们想构造一个一对一映射，在模A的陪集和模B的陪集下做一对一映射，也就是在这两个群之间做映射。如果我们可以建立这种一对一映射，使得一个群中的每一个点都能唯一映射到另一个群中唯一的一个点，这就是一对一映射。这意味着如果某个分布模这个群是均匀随机的，则模这个群也是均匀随机的。

这就是我们想证明的，我们想证明的是如下结论：对于等于Az的每一个点，其中z的取值范围是 ，意味着这是用A生成的平行多面体中的点，那么a模B也各不相同。也就是说，不存在两个a映射到了相同的点上，这等价于如果X模A是均匀随机的，那么X模B也是均匀随机的。所以如果你能在两个集合中建立这样的一对一映射，这就足以证明如果某个分布模A是均匀随机的，则这个分布模B也是均匀随机的。

上图就是一对一映射的意义，假设你有A和B，且对于任意点a，在以B形成的平行多面体中也存在着唯一的一个点与a构成映射，这就是一对一映射。下图是个反例，这不是一对一映射，因为A中的三个点在模B后映射到了0点。所以我们要证明的是，如果满足前面所说的两个条件之一，那么就构成一对一映射，而不是下面这种情况。

我们先证明第一种情况。我们假设U的行列式等于1，Oded实际上在前面的讲座中，已经用图形方法证明了这个情况。但我们这里用更理论，更数学的方法证明一下。这里B=AU，且U的行列式等于1，意味着B和A生成相同的格。我要断言，无论你怎么选择平行多面体，如果某个分布模其中一个平行多面体后是均匀随机的，那么这个分布模其他平行多面体后也是均匀随机的。U是一个整数矩阵，所以这是同一个格，所以这两个格其实是一个格。因此，如果 ，意味着两个A平行多面体中的元素将映射到模B中相同的点，这是个错误的情况，所以我们要用反证法。如果相减，我们得到 ，很简单，没什么问题。这意味着 也是B生成的一个格点，因此， 是个整数向量，因为A乘以某个向量是格中的点，意味着这个向量是一个整数向量。但是什么时候 才是整数向量呢？z的系数都是0到1之间的，不包含1，所以唯一的可能是， ，或者说 。所以实际上 和 不是模A下两个不同的向量，它们是同一个向量。这就证明了第一种情况。

我们来证明第二种情况。如果向量U是对角线全为1的上三角矩阵，那么 。证明比较类似，用同样的方法证，只不过反证的具体过程有些不同。这种情况下，我们仍然会得到 。但注意现在A和B生成的格不是同一个格了，这比较重要。我们没有限定U的系数，U的系数可以是小数，可以是根号2，我们仅要求U是一个对角线全为1的上三角矩阵，所以A和B生成的不是同一个格，它们只是行列式相同。所以我们可以把A表示成B乘以U逆，根据定义， 应该是B生成的一个格点，这意味着 是一个整数向量，因为我们乘了一个B，这是一个B生成的格点，所以这一定是个整数向量。这就构成了矛盾，大家能看出为什么吗？我们可以看到这个证明技术…好像大家没法直接看出为什么，并不是很显然，我来解释下为什么。

U是一个对角线全为1的上三角矩阵，你可以证明 也是一个对角线全为1的上三角矩阵，如果对U取逆，那么得到的也是一个对角线全为1的上三角矩阵。所以我们要证明的是，或者说我们可以看出， 是一个整数向量。这与前面的证明过程是一样的，用同样的推导过程，你就可以得到这个结论了。所以 是一个整数矩阵。我们来看看 的系数。 的系数必须是多少？一个整数，对吗？必须是个整数，但可以是哪个整数？ 只能有一个整数系数，就是0，所以唯一的可能是 。证明结束。

我们证明了第二部分，不过这意味着什么呢？U是一个对角线全为1的上三角矩阵意味着什么呢？为什么我们会得到这么一个奇怪的转换矩阵？这是因为这个矩阵与Gram-Schmidt基相关。你可以把任意基B写成Gram-Schmidt向量的形式，所以这些是 ，Oded也是这么做的。Oded进一步令这些基都正交，但是这里我们不用，没什么影响。你可以直接除以 或者乘以 不会有什么影响。所以任意向量B都可以写为一个Gram-Schmidt基乘以U，这个U是一个对角线全为1的上三角矩阵。我们的断言称，如果我们能在模这个基下产生均匀随机的点，那么这个点模这个基下也是均匀随机的。

我们做这件事的目的是什么呢？现在我们把这些结论综合一下。我们如何在一个平行多面体中产生一个均匀随机的元素呢？假设存在一个分布X，我们差不多在10页幻灯片前就提出这个问题了。我们有个分布X，这个分布模旋转后的方盒是均匀随机的，那么X模B是否均匀随机？如果A是B的一个Gram-Schmidt基，那么结论成立，这是我们前面已经证明的结论。如果这是个格，而这是个Gram-Schmidt正交基，那么结论成立，模A下均匀随机意味着模B下均匀随机。很好，没问题吧？

但这还不够，A不一定要是这个基的Gram-Schmidt基，它可以是任意一个格基的Gram-Schmidt基，所以右边是我们的格基，这个格基形状挺奇怪的，是由这两个向量构成的，但是如果这个基生成的是同样一个格，结论也成立。你会说，这个格基和这个更小更好的格基生成的是同一个格，这个格基是个Gram-Schmidt基。如果A是一个Gram-Schmidt基，这个基是从BU来的，其中U是一个行列式为1的矩阵，那么结论也成立。

我们还有结论，我们会在下面的证明中用到这个结论。如果A是任意一个整数矩阵U的Gram-Schmidt基，这里整数矩阵行列式不一定是1，有可能行列式比1还大，结论也成立，为什么？

为什么行列式大于1结论还成立？是的，但条件是U的行列式等于1，如果U的行列式大于1呢？如果格是BU，那么BU是B的子格，条件是U的行列式大于1，后面的推导就和代数知识相关了。如果某个分布模子群是均匀随机的，那么模群也是均匀随机的，所以结论仍然成立，这是因为BU是B的子格。

我们最终得到的结论是什么？Micciancio和Regev所提出的原始定理是，假设我们有C=BU，其中BU是一个格，或者是一个子格，使得C中的所有向量最大， 代表B的第n的连续极小值。假设C是这样一个矩阵，那么如果你对这个矩阵做Gram-Schmidt正交变换，那么C的所有向量最长也会超过B的 值，为什么我们能得到这样的结论？B的 值的意思是B中存在n个格向量，这n个格向量的长度都小于B的 值，所以这个基是个包含全部短格向量的格基。如果在这个格基上做Gram-Schmidt正交变换，则向量正交变换后，向量最长也不会超过B的 值，因为正交向量的长度最长不会超过原始向量的长度。因此，如果s，也就是高斯分布的参数s，大于5乘以B的 值，且如果你能在C中得到一个均匀随机分布，X分布模C下是均匀随机的，这是我们的C，如果模C下是均匀随机的，那么模格也是均匀随机的。所以这个定理表述的意思是，如果你把s选为5乘以B的 值，所得到的概率分布模格后是均匀随机的。这就是高斯分布中的参数与格参数之间的关系，我在午饭后会继续给大家讲解。这个定理给出了格参数与高斯分布参数之间的关系，也就是高斯分布中的参数s与格参数 的关系，所以我们才有可能把SIS问题归约到SIVP问题。

Chris告诉我要提醒大家注意一下。有些时候你不会用到B的 值这么一个关系的，有时我们只需要以Gram-Schmidt基的形式表达各个基的关系，所以选择X分布的具体过程，只需要对任意平行多面体，或者对任意子格，进行Gram-Schmidt正交变换就行了。所以我们实际上只需要前面这页幻灯片上的结论就够了，只需要找到U，使得对应Gram-Schmidt基的最大长度最小，小于所有可能的Gram-Schmidt基的最大长度，然后按照这个长度选定s就好了。非常好，我们用 定义了所有的相关参数，这正是我们想得到的结果，这个结果很容易理解。我们来看看这个结果怎么用，这是主定理，如果s比5B的 值还要大，那么X模B后的概率分布与均匀随机概率分布非常接近。

这里有几个图片，这几个图片是前面的讲座中贴过来的。当看图的时候我们一般不看模一个平行多面体后的图像，看这么个图可能更清晰点…如果我们把结果周期性地排布在空间中，这些峰值都代表格点，也就是不光考虑一个模平行多面体的高斯分布情况，考虑在每一个格点上构造高斯分布，不模任何值。图中显示的就是概率分布情况。这个图很明显现在不是均匀随机的，这里s变大了一些，还不是均匀随机的。

这个图中的s又变大了一些。

这个图中 ，基本上是平的了，所以这个定理可行。我们还有两分钟的时间，有什么问题吗？

对于某些格来说，s的取值要达到 的量级，我的意思是，比如 格，s的取值要达到 的量级，否则达不到均匀随机分布。

舍入误差的问题，所以你的意思是我产生了一个实数，模平行多面体，这样会出现舍入误差。是的，格中总是会有精度问题的。举个例子，对于LLL算法来说，我认为所有的学者都在研究，如何让LLL算法运行的更快，因为我们算法的输出结果具有更高的精度，所以会有一些解决办法的，但本质上精度确实是一个问题。所以你需要把精度设置的足够好，使得不管遇到什么情况，算法的精度都不影响结果。但是精度确实一个问题，如果是基于抽样的格密码学方案的话，是个问题，精度确实是个问题。还有其他的问题吗？好的。