2012年BIU密码学冬令营-05-GGH和NTRU签名的密码学分析

演讲视频简介

中间调整了一期顶会视频翻译后，我们继续更新2012年BIU密码学冬令营的讲座翻译。今天带来的是第五个视频《Cryptanalysis of GGH and NTRU Signatures》。NTRU签名一直都没有可证明安全性，但在这个工作之前，学者们也一直没找到实际的攻击方法。EUROCRYPT 2006上，Oded Regev和Phong Q. Nguyen成功完成了对NTRU签名的攻击！这个攻击再一次告诉密码学家，安全性证明是论述密码学方案安全性非常重要、更加科学的方法。

演讲视频信息

讲义链接： http:// cyber.biu.ac.il/wp-cont ent/uploads/2017/01/slides-barilan7.pdf
视频链接： http://www. youtube.com/watch? v=6_oORqAsDHA&feature=plcp
中文视频： https://www. bilibili.com/video/BV1o v41117RB/

演讲视频字幕

这是2006年我和Phong Q. Nguyen完成的一项工作。这个成果和大家之前看到的成果形式都不太一样。之前看到的成果都与LWE或者SIS相关，我们的成果是提出针对GGH和NTRU这类特定签名方案的攻击算法。希望大家会觉得这个成果比较有趣。我们非常欣赏这两个格密码学方案，它们的计算开销非常小。这两个方案蕴含了非常神奇的思想。

在讲解具体攻击技术之前，我们先来看看这两个算法的构造思想。大家能看出左下角的图是什幺吗？非常好，有的人已经看出来了，图上实际是很多点，有的人可能看不清。另一个我想给大家展示的是这个。大家看看，这是什幺呢？如果你够聪明的话应该能看出来。这不是烟花动画。大家看到的是什幺？有人说这是个正方体，大家看到正方体了吗？可能动画播放的太快了。现在看到了吗？加上框的话大家就能看的更清楚了。上次我在另一个地方也讲过这个内容，动画播放速率非常低，跟幻灯片似的。这个新电脑的性能还不错，大家可以看出来这实际上是一个立方体。这就是我们讲座中所用到的主要思想了。接下来几分钟的时间，大家就可以看到这个思想在实际中是如何应用的了。取很多点之后，我们就能够通过立方体中的点，观察到立方体的形状了。

我们回到讲座内容上来，我们首先回顾一下，什幺是格。这是一个二维格，我们之前已经见过这张图了。这里仍然是格的定义，只是带着大家回顾一下。我们有基 ，我们取这些向量的所有整数线性组合，这是所生成格的形状。相信大家已经明白格的定义了。

格中的一个基础性问题是最近向量问题，我们来回顾一下。我们不需要深入理解这个问题，了解一下就可以。给定格的一个基 ，再给定一个点u，最近向量问题要求我们找到一个距离u非常近的格点。在幻灯片上，我们知道绿色的点就是答案了。这就是最近向量问题。正如我昨天所说，这个问题似乎是一个非常困难的问题。一般情况下，如果我们试着去解决这个问题的话，已知最快速的算法要花费指数级的时间， 级的时间。这也是为什幺我们可以用格构造密码学方案的原因。接下来的几分钟内，我们就会看到方案是如何构造了的。

然而，我昨天讲过，很容易检测一个点是不是格中的点，用高斯消元法就能知道一个点是不是格点。我们只需要知道上述这两个结论就可以了。

在我讲解签名算法和攻击算法之前，我需要先告诉大家，一般来说我们如何来解决CVP问题。我估计Vadim在他的讲座中已经讲过这个算法了。这个算法是80年代中期，Babai在一篇论文中写到的。这个算法的基本思想非常简单。算法运行流程如下。我们知道我们有一个点，我们要找一个距离这个点比较近的格点。我们把给定点写为格基向量的线性组合形式。当然了，这里还是要用到高斯消元法。接下来，我们把每个系数都舍入为最近的整数。取线性组合中的系数α，这些α都是实数，然后把α舍入到最近的整数点上。这就是算法的执行流程了。α外面的这个符号的意思是取最近的整数，如果小数部分大于0.5，则向上取整，否则向下取整。是否向上取整取决于小数部分是否大于0.5。这个算法似乎是可以正常执行的，条件是给定的基向量要比较好，要比较短。

我们来看一个动画。我这里要分析一下这个算法。虽然现在我们还用不到这个算法的分析结果，我这里先简单分析一下，为周三的讲座内容做准备。现在讲解分析结果也是个不错的时机。

我这里实际上用图片的形式，直观给大家讲解一下这个算法的工作原理。我们想知道的是，多大范围内的点可通过这种算法正确找到距离最近的格点。这也是这一张图要给大家展示的内容。我们取一个格，我们已经有了一个很好的格基了，给定的好格基就是几乎互相正交的两个格向量。这个算法所做的工作是什幺呢？它取空间中的任意一点，用格基的线性组合表示这一点，并对坐标值进行舍入。如果你稍微想想算法的工作原理，会发现映射到0点的点集就是基向量线性组合系数在-0.5至0.5之间的点。如果你再仔细考虑一下算法的工作原理，你会发现实际上就是蓝色区域的点。也就是说，蓝色区域所在的点，可以通过这个算法映射到中间的格点。这些点实际上就是用格基的线性组合表示后，各个系数均在±0.5之间的点，应该很容易看出具体的原因。这就是当使用好格基时，算法所能给出的结果。

如果你有一个不好的格基，用相同的算法求解。如果你有一个不好的格基，你所面对的情况也就不一样了，这个算法的输出结果会变得非常糟糕。当我们有这样一个格基的时候，当然了，情况可能会变得更加糟糕。很显然，格基向量的长度变得非常长。我这里只是给大家形象展示一下所发生的情况。现在有个比较长的格基向量，格基所对应的平行多面体形状并不理想。蓝色区域非常的长，其所包含的点可能离中心点非常远，如左下和右上区域的点。这些点仍然会被映射到平行四边形的中心点，而中心点是离它们非常远的格点，这些点不能被映射到离它们距离比较近的格点上。通过这种方法映射，输出的结果并不理想。这一结果的原因是格基比较差，这个算法实际上没有做任何其他复杂的操作，只是对系数舍入，算法输出结果不理想也是很正常的。

现在我们来简单分析一下这个算法，虽然在接下来的讲座中，我们应该用不到分析结果。如果你没理解下一页幻灯片的讲解内容，也没关系。我们来想一想，大家应该抬头看屏幕上的图，因为好像我给出的讲义中并没有相关的提示信息。我们现在想做的是，求出通过这个算法可以正确映射最近点的半径范围。也就是说，离中心格点距离有多近的点，才可以通过这一算法正确映射到中心格点。

这是一个非常重要的动画演示，红色区域就是可以正确映射的点集范围，这也是可以正确对点进行映射的最大半径范围了，而这个半径值应该和基存在函数关系。如果我有一个好的格基，我应该能得到一个半径比较大的球。如果我有一个不好的基，我应该得到一个半径比较小的球。一般来说，这个球的半径都比较小。红色球中的黄色箭头就是球的半径，就是通过算法可正确解码的点集范围。我再强调一下，这个分析结果和后面的讲座内容无关，但我认为这个分析结果对理解周三的讲座内容会有帮助，因为我这里要引入一个结论，这个结论是从线性代数中引申而来的。就像Gram-Schmidt一样，这并不是格中特有的结论，不过这个结论非常有用。这个结论是从线性代数中来的，而这个结论和格有很重要的关系。

这个关键定义是对偶基。如果你有一个基，这里的基指的是线性代数中的基。如果你有一个基 ，你可以定义对偶基。我们现在暂时忘记格的内容。对偶基的定义非常简单，我们按照如下方法定义对偶基。对偶基表示为 ，或直接用 表示。任意一个向量都与 正交，其中j不等于i，但与 的内积结果等于1。在不看讲义内容的情况下，大家试着想一想对偶基如何来帮助我们分析算法。我们试着想象一下，我有这幺一个基 ，它与其他所有的 都正交， 与 的内积结果等于1。可能有点难想象，总之这就是对偶基的定义。

对偶基有很多有趣的性质，比如对偶基的对偶基就等于原始的基。我们可以举一个特殊的例子。如果我们把B写为列向量为 的形式，那幺这个基的对偶基就是B的逆转置。很容易看出其中的原因，我们取逆，这样行向量和列向量就满足内积的限制条件了。再求转置，列向量和列向量就满足内积的限制条件了，很容易验证这一点。

为什幺要讲对偶基呢？因为我们要用到对偶基的一个性质来帮助我们对算法进行分析。如果你有一个向量u，在右边我们把u写为 ，我们可以很容易地把 写为u和 的内积形式。对偶基可以帮助我们通过基 求出u用B的线性组合表示下的系数。这都是线性代数的知识，相信大家在以前的学习中也遇到过。这就是对偶基的使用方法了，很容易知道为什幺可以得到这样的结果。我们只需要把u带入，把u展开，你就会发现所有其它的 都被消去了，唯一剩下的就是 ，而 等于1，我们本来就是这样定义对偶基的。

现在我们知道对偶基可以帮助我们求任意向量在基B下的线性组合结果。为什幺这个结论很好呢？因为我们可以等价地把Babai算法的输出结果写成下述形式。给定一个点u，我们做如下事情。点u在 下的线性组合系数就等于u和 的内积舍入结果。这样，我们就不需要将u用B展开，从而得到各个系数值了。实际上，我们只需要求内积结果，就能得到各个系数。通过这种方法表示算法的输出结果会更简洁一些。

一旦我们把结果写成这种形式，我们就可以很容易地得到半径值了。我们来看看半径值等于多少。我们试着看一看，距离原点多远的点仍可以通过算法正确映射。如果点可以映射到原点上，那幺所有这些系数都应该等于0，所有这些舍入系数都应该等于0。换句话说，所有与 的内积结果都应该在±1/2之间。也就是说，映射到0的点集区域是用 表示的某一平面，这实际上就是我们前面那张示意图展示的结果。我们已经看过前面的图了，我们切到前面的幻灯片。可以看到，正确映射区域就是基与对偶基的重叠部分，每一个平面都由 所确定，而 就是所得子空间，或者说超平面边长大小的1/2。

这就是我们前面所问问题的答案了，因为我们要求的半径就等于所有这些向量的最长向量长度。为什幺呢？因为每一个向量都对应一个切面，而这个切面的权重等于 ，而我们可以正确映射的点集半径也是这个值。也就是说，这一区域的最小值等于 。这个等式告诉了我们半径值，也就是可以正确映射的点集半径。

我想说的是，Babai算法实际上已经在实际中得以应用，比如在蜂窝移动通信中就有重要的应用。但在这里，在给定好格基的条件下，我们可以用相同的算法求最近格点，算法和LLL类似。当格基比较好时，算法可以输出比较理想的结果。这些算法已经在MIMO或者类似的系统中得到应用了。当然了，这个结论不是我们这次讲座的主要内容。

我最后想强调的是，我讲这个内容是为周三的讲座做准备的。当我们知道了对偶基，你可能会问一个很自然的问题，这个基能生成一个格吗？当然可以，对偶基也构成了格。对偶基也是格基，拥有n个线性无关的向量。我们很自然地将对偶基所生成的格称为对偶格。我昨天没有讲对偶格的相关内容。实际上，对偶格和我们所学的很多格知识相关。对偶格的概念也非常重要。在周三的讲座中，对偶格起到了关键的作用。我们会在周三的讲座中再次遇到对偶格，我会在周三的讲座中详细讲解这部分内容。我想说的是，对偶格的定义非常有意思。你可以对格取不同的格基，不同格基的对偶格基所生成的格是同一个格。当你定义了一个格时，我们也可以定义这个格的对偶格。对偶格也有很多有趣的性质，有很多相关的定理，我们都可以试着证明一下。当然了，这些都不是今天讲座的主要内容。有关今天的讲座，我们需要知道的是，如果有一个好格基，你就可以解决CVP问题。即使没有一个好格基，你仍然可以很容易判断某点是不是在格中。

我们来快速回顾一下数字签名方案的定义。我这里不会为大家讲解形式化定义，相信大家已经看过很多遍数字签名方案的形式化定义了，我这里快速回顾一下定义。

数字签名包含三个算法。密钥生成算法输出公钥和私钥。签名算法以消息和私钥作为输入，输出消息对应的签名。验证算法只需要公开的信息，验证算法以公钥、消息、签名作为输入，验证算法可以验证此签名是否是给定消息所对应的签名。这是从算法的角度来描述数字签名。

虽然签名算法的安全模型非常重要，但在这里我不会讲解安全模型，原因是我们这里并不是要构造一个签名方案，而是要破解一个签名方案，而且大家也会看到，破解方法和安全定义有对应关系。我这里不会讲解安全定义，否则大家会容易混淆。你需要知道的是，我们有很多种方法可以定义签名方案的安全性。安全模型是一个非常重要的概念。我这里还要指出，可以黑盒构造一个数字签名方案，可以通过单向函数构造数字签名方案，这可以追溯到Bellare的一个成果。Vadim和Chris昨天也应该讲过了，我这里强调一下。我们可以利用单向函数构造一个安全的数字签名方案。这个结论很有用，但是不存在直观的方法让方案的效率更高，而这正是我们现在正在研究的一个重点问题。Vadim在这几天的讲座中也会提到，在格密码学领域，构造可证明安全的数字签名方案仍然是一个重要的公开问题。当然了，这里指的是构造高效的数字签名方案。你可以看到，我们所破解的这个算法，签名的长度小于2000比特。在我们所构造的数字签名方案中，这是一个非常高效的方案。

好了，现在我们已经知道数字签名的定义了，我们来看一看我们要攻击的这个签名方案吧。这个方案的构造要追溯到1997年。这是由Goldreich、Goldwasser和Halevi提出的一个签名方案。实际上这并不是一个具体的签名方案，而是一种签名方案构造框架，可以用这个框架构造多种数字签名方案。我们可以用不同的格来实例化签名方案。这个框架的基本思想非常有趣，很多可证明安全的格签名方案都借助了这个框架的基本思想。但是，光有框架不行，我们要求具体方案也应该是安全的。这个具体的签名方案没有安全性证明，无法把方案的安全性规约到某一个困难问题上。正如你们所见，这个讲座的内容确实指出了方案的缺陷，所以这个方案才没有对应的安全证明。这个签名方案存在一个严重的问题，不过方案的基本思想是非常有用的，其他格签名方案的构造也用到了这一基本思想。这里的基本思想是，如果没有一个好格基，CVP问题就是困难的。如果有好格基，CVP问题就是简单的。我们之前也讲到这个结论了。如果有格的一个好格基，你就可以找到临近格点，这也是方案思想的来源。这是一个非常有趣的思想。

我们来看看签名方案是如何使用这个思想的。我们来讲一讲具体方案。先从密钥生成算法讲起。你生成了同一个格的两个格基，你选择一个格，并选择两个格基。私钥是好的格基，这个格基比较短，格基向量基本上是正交的。公钥是相对不好的格基。这里也涉及到一些细节问题，比如如何选择这两个格基。实际上，它们给出几种选择方案。后面大家也会看到，NTRU给出了更高效的格基选取方法，不过格基的选取和今天的讲座内容无关。我们有很多格基的选择方法。这里有一个非常好的坏格基选择方法。给定好格基，把它转化成Hermite正规基。昨天Vadim应该提到过这个概念。这种格基选择方法是Micciancio在随后的几年中发现的。总之，你要选择一个好格基和一个坏格基。

如何进行签名呢？如果你有一个消息，比如某人给了你一封电子邮件，你想对电子邮件签名。你有签名算法的私钥，你有一个好的格基。你首先需要进行映射。这是签名的标准步骤，我们要通过所谓的随机预言模型，用一个哈希函数对消息进行映射。你把消息映射为空间中的点。我们这里把消息看成空间中的一个随机点，实际中的确可以实现这一映射过程，把消息看成一系列坐标值即可。现在，你使用Babai算法找这个点的一个临近格点。因为你有一个好格基，你有签名方案的私钥，你可以做到这一点，你可以借助好格基找到一个临近格点。最后，你得到了消息和签名。

你想验证签名结果是不是正确的，你要做的工作非常简单。首先检查签名结果是不是一个格点。正如我最开始所说的，即使没有好格基，仍然能验证点是否是格点，只需要调用高斯消元法。第二件事就是检查签名结果与消息的距离是不是足够近。这也很容易做到，取两个坐标的差值，求差值向量的范数即可。我们很容易检查范数的大小，很容易求得两点之间的距离差值。

这就是签名方案的基本思想了，我画了个图来演示签名的基本思想。我们有两个格基，私钥是左上的这个好格基，公钥是左下的这个比较坏的格基，但仍然是格的基。公钥只用于验证算法，用于检测签名结果是不是一个格点。我有一个电子邮件，我只需要把邮件映射为空间中的一个点。想象一下映射的点就是这个黄色的点，这就是我的消息。如果我想签名的话，我就使用Babai算法，我就得到了蓝色的那个格点，这个格点是平行四边形的中心点。这个格点与消息的距离很近，因为我是通过一个好格基作为输入计算得来的。

现在，我们不再需要私钥的帮助了，我们只用公钥就可以对签名进行验证。我要做的是，检查签名是否确实是一个格点，我可以很高效地完成此检查。随后，我求出两个点之间的距离，并检查所得的距离是不是比较小。这就是基本思想了。

这个想法看起来还是挺有道理的，方案安全性基于某个困难问题，也就是CVP问题。不过这个表述没有什幺意义，只能说方案的安全性与CVP问题相关，我们无法证明方案的安全性。但是这个方案让我们觉得，安全性和CVP有一定的关系。而CVP问题是一个困难问题，这个问题的解决时间是指数级的。

我们接下来看看NTRU签名方案。这是在我们的论文发表之前，维基百科上NTRU签名方案的描述。本质上，NTRU方案是一个非常复杂、算法描述非常清晰的GGH签名方案实例。NTRU建议在GGH方案中使用一个特定的、具有非常多优秀性质的格。这个方案的构造非常精妙，方案的运行效率高得令人惊讶。你只需要用很少的比特数来表示出这个格。这个格在现在仍得到了广泛地应用，不过在那时，NTRU公司建议在签名方案中使用这个格。

我们来看看具体细节。这个格最初是2001年，由Hoffstein、Howgrave-Graham、Pipher、Silverman和Whyte在论文中提出的。这是GGH签名方案的一个非常高效的实现方法。我这里不会给大家讲解具体的细节。这个格的构造非常复杂。用相同的格维度所构造出方案的签名长度会非常短。实际上签名长度小于2000比特，如果用字节(B)或者千字节(KB)为单位描述的话，看起来就更短了。人们非常关注签名长度的原因是，人们需要把签名结果存放在小的芯片中，而芯片的存储量一般比较小。这个方案签名消耗的存储量很小，计算效率非常高，计算效率甚至比基于RSA的签名方案还要高。我不会讲太多这个格的细节，如果想了解这方面内容，可以参考IEEE发布的相关标准，我估计现在这个标准已经被废除了。在2002年，学者们已经指出了签名算法的一些缺陷。但在那时候，人们仍然认为NTRU方案是一个安全的签名方案。

有关NTRU我就介绍到这里，下面来看看我们的主要成果。我们的主要成果是，我们找到了此类签名方案的内在缺陷。这是所有GGH类型签名方案的一个严重的安全缺陷。后面你会发现，这个缺陷利用起来并不困难。实际上攻击算法非常简单。可能当时人们没有观察到这一缺陷的主要原因是，我们从一个不同的角度来考察NTRU签名方案的安全性。我们更多地是从几何角度，而非代数角度考虑NTRU签名方案。我想这就是之前人们没有发现这一缺陷的主要原因吧。当然了，我这个讲座的目的是告诉大家，方案的安全性证明是非常重要的。在构造签名方案时，我们需要证明构造方案的安全性。对于任何密码学构造来说，都需要类似的安全结论。

我们的攻击也经过了实验的验证。我们在高维度下对GGH方案进行了攻击，格的维度是400维。同时，我们对502维的NTRU签名方案成功实施了攻击。我们本以为实验过程会很久，我们用了多个处理器进行并行计算。实际上，攻击算法运行得非常快，只花费几分钟的时间，借助400个签名结果的帮助，就可以正确恢复出私钥。

我们马上就会讲到具体的攻击算法了。这个攻击的前提是，你要得到一系列消息签名对，通过这些消息签名对，提取出签名方案的私钥。我们马上会详细讲解具体攻击过程。当然了，我们后面也会讲到，攻击时间取决于签名方案的参数。总之，攻击速度非常快，可以很快找到签名方案的私钥。

我后面会具体地讲，但现在先提一下，有一些针对此攻击的抵抗方法。我后面会介绍如何提高这个签名方案的安全性。如何对签名算法进行修改，抵御此类攻击，比如对结果进行扰乱，增加私钥的条目等等。

我认为，这个讲座最重要的是给大家展示了签名方案可证明安全的重要性。Chris在今天后面的讲座中也会讲到，我们通过几年的时间，利用矩阵的一些性质构造了可证明安全签名方案。从概念上讲，所构造方案的基本思想是一样的，但是你需要使用一些特殊的方法来避免此类安全缺陷。

需要指出的是，我们确实找到了一种攻击算法，但这个攻击算法不能破解所有格密码学方案。你们昨天看到的方案和困难问题，SIS和LWE问题，它们仍然是安全的。这个攻击算法只能针对特殊的格密码学系统实施攻击，并不能用这个算法攻击其他格密码学系统。特别要指出的是，同样是NTRU提出的一个格加密方案仍然是安全的。这个攻击方法只针对NTRU和GGH签名方案，对其他的方案不适用。

终于要讲到攻击算法了，相信大家都已经准备好了。

现在请大家不要看讲义上的内容。我在讲义中藏了一些内容，幻灯片上将用动画来描述攻击算法。攻击过程如下。我们来看看幻灯片的动画。我们有了一个签名方案，我们对一个消息进行签名，得到了消息的签名结果。换句话说，签名算法找到了一个临近格点。我们不知道私钥是什幺，因此我们看不到格的样子。我们只有公钥，我们不知道格的几何形状是什幺。我们所能看到的只是两个点，我们不知道格的几何结构。我们只能看到两个点，其中一个点是签名结果，也是一个格点，另一个是离格点很近的消息点。我们接下来能做什幺呢？我也不知道，我们先把这对结果放在一边。我们取这对结果，把它放在左边，用到的时候我们再从左边取。

我们还可以得到一个消息和对应的签名。我们有理由相信，某人或者某公司可以对另一个消息进行签名。我们还可能得到其他消息的签名结果。我们不知道如何利用这一结果，暂且也把它放在一边。不过和之前一样，我们把两个签名结果放在一起。大家可能已经明白我接下来要做什幺了，我们把签名结果都放在一起。这是可以做到的，因为签名只是一个向量。我们再取两个点，求向量，也就是求两个点的差值，把差值结果放到一边。我也不知道这动画什幺时候是个头，我忘记我放了多少个了。动画应该能结束的，如果你有讲义，麻烦告诉我放了多少个消息签名对。

但是可能大家已经发现攻击算法的基本思想了。基本思想是，当我们得到足够多的点，这些点的结果就形成了一个形状，而这个形状实际上就是Babai的解码区域，这实际上就是签名算法签名时用到的格基所对应的平行多面体。我就不再放一遍动画了，大家可以想象一下，一旦我们得到了足够多的点，我们就可以慢慢看出点所构成的形状了。现在的问题是，我们是否能从大量随机取点结果中恢复出几何形状？

本质上，攻击算法的基本思想是，获得很多签名结果，取签名结果和对应消息的差值，把这些差值向量都汇集在一起，我们就利用这些差值向量完成攻击。我把这个问题称作隐藏平行多面体问题。如果我们能解决这个问题，攻击就成功了。给定从n维中心平行多面体中随机采样的点集，求平行多面体。直观上看，我们可以解决这个问题。如果对高维空间有所了解，会知道高维空间上的问题会变得比较困难。高维空间中，我们有指数级的向量方向，格问题会变得非常困难。高维空间中，所有问题都会变得比较困难。但正如你所看到的，在高维空间中，我们是可以解决这个问题的。一旦我们可以解决这个问题，我们就可以破解签名方案了。

来看看如何解决此问题。在幻灯片上的图中，我们采样了很多点。但令人惊讶的是，在实际攻击中，即使在高维空间实施攻击，如在500维上实现攻击，我们仍然只需要400个点。这实际上是一个很细节的结论，William Whyte给出了相关的分析结果。总之，这就是我们攻击算法的直观想法。我们要根据采样点集，找到一个能把它们都包含进来的平行多面体。

我们先解决一个相对简单的问题，给定立方体中的采样点，找出原始的立方体。我们现在针对一个特定的问题求解。我们暂时不去担心平行多面体的问题，只考虑立方体，但是这个立方体的边不落在x-y轴上，立方体经过旋转了。这是我们现在想要解决的问题，这个问题看起来并不是很困难。

这里有一个二维的观察结果。我们有很多从立方体中采样的点，我们可以观察到一个正方体，我们想要具体求得这个正方体的表达形式。大家都已经能看出正方体的轮廓了。不过在高维空间中，我们得需要一个具体的算法来求解问题。

先来看看我们尝试的第一个想法。这个想法非常自然，但实际上这个想法不可行。我们称这个想法为概率分布协方差。相信大家在本科到研究生之间学概率论时听说过这个名词。这个想法是，把x看做从立方体U中均匀选取的点，x是我们采样的向量。随后，我们选择一个特定的向量u，我们把u看成一个固定的向量。我们现在想做的是，求沿向量u方向的概率分布协方差。怎幺求协方差呢？我把概率分布映射到u上，我只需要求采样与u的内积。我们要求的是内积平方的期望值。我们求内积的平方，取结果的期望值，这就是采样与u的内积平方期望。我这样计算的目的是，我想看看在特定向量方向上，协方差是否会有所变化。如果有一定变化的话，我可能就能从结果中发现立方体的表示方法了。如果计算得到采样与u的协方差，甚至有可能直接得到立方体的表示方法。这就是我们的基本想法。

但当经过简单的计算后，我们会面临一个问题。这种计算方法过程并不复杂，我会给大家介绍下，后面我们会看到更复杂的计算过程。x是什幺？x是旋转立方体中的采样点，我们可以把x写成Uy的形式，其中y是标准立方体中的采样点，是 中的采样点，这是一个标准立方体。而U是我们要计算的矩阵，是旋转后的矩阵，所以x等于用旋转后的矩阵U映射标准立方体，y是标准立方体中的采样点。

现在，我们试着计算采样点与u的协方差大小。u的协方差等于什幺呢？按照上述定义，协方差等于内积平方的期望值，而这里的内积是x和固定向量u的内积结果。我们可以把协方差表达式展开， 等于 ，也等于 ，我们可以把结果写成 。我们来看看x的值，x等于Uy，所以我们可以写为 。注意到U的值也是固定的。如果我们把协方差写成这种形式的话，只有y是变量，我们可以把U提出来，这一步没有什幺问题。所以现在我们只需要对中间的矩阵求期望，这就容易多了。 实际上是一个矩阵，因为y是一个列向量，但是这一步推导很容易，每一步都是正确的。我们最后得到的是 。

如果你计算矩阵 ，实际上这个期望值等于1/3乘以单位矩阵，也就是对角线上都是1/3的矩阵。为什幺呢？我们先想一想 是什幺？ 是一个矩阵，其中位置ij等于 。但想一想y的定义，y中所有坐标都是相互独立的，y中的每一个坐标都是从[-1,1]中独立选取的。非对角线上的所有元素期望值都等于0，因为 等于 ，这两个期望值都等于0，我们只剩下对角线上的元素。而对角线上的元素等于1/3，因为随机变量的平方期望值等于1/3，这也是随机变量取值的方差。很好，我们完成了计算，接下来要处理的是u和 。这两个矩阵都是正交矩阵，U是一个正交矩阵，我们可以消去它，最后剩下的是 。而u是一个单位向量，所以 等于1，最后我们得到的是1/3。最后我们得到的是，对于所有的特性向量u，其协方差都等于1/3。这可是一个糟糕的结果，这意味着从协方差中我们无法获得任何信息。我们希望通过对u进行变换，使得协方差的值可以发生改变。我希望看到一些变化，但实际上得不到任何有用的信息。

我想直接讲第二种方法，估计大家已经知道大致方法是什幺了。这是我们的第二个尝试，我们这里不取二阶矩的值了，我们取一个可以获得信息的阶矩。这里的思想是用四阶矩替换二阶矩。实际上，我们重复了第一种方法的处理过程，只不过我们这里不取二阶距，而是考虑 。我来简单讲讲这里的直观想法，这里的计算过程并不复杂，可以作为私下练习。

大家可以尝试计算一下，然后你会发现，四阶矩的值取决于向量u的方向。四阶矩的具体形式是这样的。四阶矩等于1/3 – 2/15乘以坐标值4次方的和。这意味着什幺呢？我把意义写在了幻灯片的下方。如果u的方向指向了立方体的其中一个角，那幺在向量u中，每一个坐标都等于根号n分之一。每一个坐标的值都严格等于根号n分之一，那幺对u_i求4次方再求和，就等于n个根号n分之一的4次方求和。因为每一个坐标的值都等于根号n分之一，所以坐标值的4次方求和就是这些根号n分之一的4次方求和，求和结果等于1/n。这是一个非常小的量值，因此四阶矩约等于1/3。如果向量u指向了立方体的角，所求的四阶矩结果等于1/3。如果向量u指向了立方体的表面，那幺u的坐标类似是(1,0,0,0,0,…)这种形式，从旋转立方体的表面上所选择点的坐标等于(1,0,0,0,0,…)这种形式，此时四阶矩结果等于1/3-2/15，也就是说等于1/5。这个结果就比较好了，我们可以看到差别，点指向立方体表面和点指向立方体角所得的四阶矩结果不一样。这是一个好消息，没准我们可以通过这种方法求得立方体的方向，这正是我们所做的工作。

这两个图解释了为什幺我们会得到这样的结果。从公式中我们是无法直观看出原因的。直观解释是这样的。如果向量指向了立方体的表面，如果我有一个立方体，从中采样点，我们得到了一个指向立方体表面的点，这个向量所指方向的延长线实际上会穿过立方体的表面。如果我们把概率分布投影到这个方向上，观察 的概率分布，所得到的概率分布非常简单，结果就是[-1,1]的均匀分布。大家可以思考一下，如果我沿着立方体的轴进行投影，所得结果就是[-1,1]的均匀分布，因为每一个坐标值都独立服从[-1,1]的均匀分布。但是另一方面，如果我沿着指向立方体角的向量进行投影，我的向量不再指向立方体的表面了，而是指向立方体的角时，考虑内积结果，你得到的结果是n个独立随机分布的变量求和，每一个变量都服从[-1,1]的均匀分布。如果你还记得线性定理的话，如果我对满足独立均匀分布的变量求和，那幺所得变量会满足正态分布，也就是我们上图的分布。我们可以很容易得到这样的结论，沿着任何一个向量投影概率分布，所得结果都近似等于正态分布。当变量满足[-1,1]的均匀分布时，正态分布的四阶矩与二阶矩是完全不同的，这也是为什幺在峰值时四阶矩结果会有所不同的原因。在二阶矩下，我们看不到任何变化，因为所有变量的二阶矩结果都相同，我们会得到相同的二阶矩。但幸运的是，四阶矩会有所不同。这方面我们就讲到这里，现在我们来试着恢复一下立方体的方向，我们试着来解决前面提出的问题吧。

算法的思想看起来借鉴了统计思想，还借鉴了一些观察结果。我们来总结一下，这就是算法了。我们先挑选出一些随机的向量方向，来试着得到最小峰值。我想说的是，我们可以计算出峰值，我们只需要计算x的期望就可以了。我们有x的采样结果，我们可以试着计算x的期望。也不是严格计算x的期望，而是进行估计。

我们来看看算法是如何工作的。我们执行梯度下降算法，对u进行平移，直到找到四阶矩的峰值结果。我这里不会讲解算法的具体细节，大家可以自己想一想算法细节。我们取一个u，可以对u进行变换，使四阶矩变小。我们需要保证Kur函数不出现计算错误。我们需要通过一些方法处理计算错误，不过如果你的算法设计的足够小心，u总能到达立方体的表面。现在，每次你执行映射算法时，你就得到了2n个指向立方体表面向量中的一个。我们执行n次映射算法，经过一段时间后，我们得到了所有的立方体表面，也就知道立方体的方向了。这样我们就讲完了如何通过攻击算法得到立方体的方向。我们需要进一步指出，如何推广攻击算法，得到一般平行多面体的方向。现在我们已经把最难的地方讲完了，我们不再讲更难的内容了。来简单看看直观思路吧。

我们已经知道的是，任何平行多面体都可以写成下述形式。x是平行多面体的采样点，你可以把x表示为Ry，R是生成平行多面体的向量矩阵，也就是向量的基。我们昨天已经讲过平行多面体了。而y就是各个坐标满足[-1,1]均匀分布的点了。所以平行多面体可以看成用R对立方体进行变换。但现在的问题是我们不知道R，我这里写出来了。实际上你可以恢复出R，你可以很简单地从采样点中恢复出R。给定采样点，你可以知道平行多面体的形状。对于平行多面体来说，我们还是要用到二阶矩的，要用到在立方体中无法使用的二阶矩。在平行多面体中是可以用二阶矩的，二阶矩能帮你把问题转换为立方体中的问题。

我们来看看具体如何操作。考虑一个矩阵 ，这个矩阵叫做协方差矩阵。我们取 。我们把 展开，x=Ry，我们之间已经见过类似的推导过程了，你得到的是 。我们已经知道 等于什幺了， 等于1/3乘以单位矩阵。等式中还剩下的是 ，现在R是一个任意的矩阵。接下来，我们需要进行估计了。我们可以估计出 ，我们可以取很多x的采样结果，估计出 ，这个期望结果会告诉我们 的近似值。很好，我们现在有 了，但我们没法直接使用 。我们令 ，这是我们可以计算得到的值。有些时候，我们称S为R的格拉姆矩阵。从某种程度上，S可以认为等于 。我不知道大家还记不记得下面的代数和矩阵相关知识。现在我们要做的是考虑矩阵 ，我们可以很容易计算一个矩阵的-1/2次方，得到另一个不同的矩阵。然后你取 ，先不用考虑我们是否可以进行这样的计算，但我们可以注意到，如果在 上乘以R，所得的结果就是一个正交矩阵，这是基础线性代数的知识。如果我们把 展开写，就能发现得到的是一个正交矩阵，因为我们在这个矩阵上乘以其转置，得到的结果就是单位矩阵。

为什幺这个结论很有用呢？因为这个结论告诉我们 是一个很好的矩阵，而这就是算法的主要思想。将任意平行多面体用 转化，实际上是在做下述事情。取一个平行多面体，把它压缩成一个立方体，这个立方体的形状可能不太好，但至少是一个立方体。之所以能达到这样的效果，原因如我前面所说， 是一个正交矩阵。由于它是一个正交矩阵，而我们又拥有很多采样点。如果我们用 转换x，我们得到的点等于 。由于 也是一个正交矩阵，所以我们实际上把立方体旋转了一下。希望大家以前遇到过这样的转换方法，给没见过这种方法介绍下，这种方法实际上对矩阵进行了一个有意义的转换，实际上就是把一个平行多面体转换成为了立方体。

现在我们可以运行之前介绍过的算法，找到立方体的方向和表达式。找到立方体的表达式后，在结果上乘以 ，恢复出R，这就是攻击算法了。

在讲座结束前，我还想给大家讲一个相关的故事。这个事情发生在会议投稿截止日期的前两天，Farm MacArthur给我打了个电话说，你一定要去看一本书。我手头没有这本书，于是我跑到图书馆看了一下这本书。这就是那本书了，这本书的名字是《独立成分统计与分析》。我不知道他是怎幺找到这本书的。这本书我越看越觉得担忧，这本书中描述了一个非常类似的问题。统计学家可能早就遇到过这个问题了，他们因为另一个不同的原因而发现了这个问题。这实际上很有趣，这个算法在统计学中也有非常有趣的应用。这个算法在统计学上叫做独立成分分析，缩写是ICA。大家可能听说过PCA，PCA是个非常着名的统计学方法，而ICA实际上就是高阶矩下的PCA。统计学中的一些算法和我们提出的算法很类似。这个算法并不是毫无用途的，这些算法在实际中已经得到了一些应用，我们很高兴地看到在之前已经有人发现并使用了这类算法，而这类算法的应用场景非常有意思。

这就是这类算法的应用场景。实际上，在网站中还有算法的相关演示。这个算法的应用场景是这样的，应用场景叫做“鸡尾酒会问题” 或者这个问题的变种。现在有一个酒会，里面有很多小组织，成员互相之间在交流。比如有3个小组织，每个小组织的成员都在单独交流。我们想知道他们交流的内容是什幺，于是我们在房间里面放置了很多麦克风。当然了，你不可能把麦克风安装在交流地点，只能这里放一个，那里放一个。每个麦克风收到的录音都是各个小组织交流声音的叠加。比如某个麦克风收到了第1个组织1/2音量的交流内容，收到了第2个组织1/3音量的交流内容，收到了第3个组织1/8音量的交流内容。每个麦克风的录音中都混杂了多个交流的内容。他们要用这个算法完成什幺工作呢？他们要分离出各个小组织的交流内容。他们要通过一系列麦克风的录音结果，比如3个麦克风的录音结果，恢复出各个小组织的交流内容。这实际上是一个非常好的应用场景。你从各个信号源获得录音结果，你没法从录音结果中得到什幺信息，因为录音结果混杂了3个交流内容，可能还有更多的交流内容，比如5个或者6个。通过执行算法，我们可以把各个交流内容分离开。这是一个非常好的算法应用场景，这就是统计学的应用场景了。

算法也用在了学习领域。当然了，学习领域涉及的变量不同，场景也不同。Frieze、Jerrum、Kannan在1996年发表了一篇相关的论文，这类算法也被应用于学习领域。这就是算法在其他领域的应用。但在我们的论文中，你可以看到这类算法的严格分析。在这之前，这类算法并没有被用于密码学或密码学方案攻击领域。我们所完成的工作还是很有趣的。

最后几分钟的时间，我来讲讲未来可以做的一些工作吧，这也是最重要的一部分内容了。我们未来要研究什幺呢？我们有了一个签名算法，但是我们把这个算法破解了。但我想说的是，这并不意味着末日的到来。NTRU也给出了一些相关的建议，叫做“扰乱”。如何修改签名方案，使得方案变得更加复杂？他们建议取多个平行多面体，在上面叠加更多的噪声。方法是执行两次Babai算法，把消息点舍入到另一个平行多面体中，看起来像是这样。

他们取两个平行多面体的Minkowvski和，这种方法似乎可以让方案变得更复杂。我不知道如何证明方案的安全性，这种方法也不是可证明安全的。最近，Léo Ducas和Phong Q. Nguyen完成了一项工作。他们指出，即使执行扰乱，攻击者还是可以获得一个好的格基。所以很明显，这种方法不足以让签名方案抵御攻击者的攻击。我们需要其他的签名方案，我们需要安全性更强的签名方案。Chris的讲座中会讲到如何获得安全性更强的签名方案，这是Craig、Chris和Vinod的成果，如何构造真正可证明安全的签名方案。方案的主要思想是遵循GGH的构造框架，他们提出的方案用到了一个重要的思想，称为高斯采样，来避免安全问题，攻击者不能根据临近点得知秘密基的形状了，而这正是我们想解决的问题。我们在Chris的讲座中将看到具体是如何实现的。

这就是全部的内容了，非常感谢。