Press "Enter" to skip to content

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的讲座中将看到具体是如何实现的。

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

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注