2012年BIU密码学冬令营-04-Basic Cryptanalysis-第1部分

演讲视频简介

我们继续更新2012年BIU密码学冬令营的内容。这次的讲座为第04期，Vadim Lyubashevsky讲解了格密码学中的密码分析技术。格密码学中最基础、也是最有用的密码分析技术就是传说中的LLL算法了。应用LLL算法，我们可以知道在什么条件下，格问题是困难的，在什么条件下，格问题是简单的。由于LLL算法是多项式时间算法，我们也有理由相信，LLL算法无法解决的格问题实例大概率是困难的。因此，LLL算法也能告诉我们应该怎样设置格的参数。

第04期长度为80分钟。按照惯例，我们仍然将讲座拆分为两个部分。第一部分主要介绍LLL算法及其在子集和问题中的应用。第二部分主要介绍LLL算法在SIS问题和LWE问题中的应用。本文章是第一部分的内容。Vadim Lyubashevsky讲座中频繁出现提问与回答过程，本文章将中间打断的提问回答部分删除，只留下主体讲座内容。如果对完整视频感兴趣，还请知友们移步B站观看完整视频。

这次修正和更新视频的过程中，我也是终于大概了解到了格密码学究竟是个怎么回事。格相对来说的确很难理解。这个领域既需要比较扎实的抽象代数、线性代数知识，又需要比较扎实的计算复杂性理论基础，还需要理解可证明安全密码学，最好还要知道如何用程序实现相应的运算。希望翻译工作能为苦苦挣扎在格密码学领域的知友们带来一些帮助。

演讲视频信息

演讲视频字幕

欢迎来听第二天的讲座。昨天大家已经了解了一些格中的问题，SIS问题和LWE问题，以及很多密码学系统，应该说是所有的格密码学系统，可证明安全的格密码学系统本质上都基于SIS问题和LWE问题。因此，我们最好要了解的内容是，如果你要构造格密码学系统，如何设定格的参数？

这个问题非常重要。以前，人们总说某个密码学系统的安全性基于LWE、SIS问题。你也知道这些假设都具有最糟糕情况归约，把这些算法实例化，安全性就特别高了。但是现在，格密码学得到了越来越多的关注。它已经可以为现实中所用，至少是一种密码学备选方案了。我们最好应该知道，如何设定参数来实例化格密码学系统。

这是我们今天要讲解的内容：基础密码学分析。这些知识都非常基础。好消息是，我们需要知道的可证明安全的密码学分析技术，就是这个基础密码学分析，不用知道其他的了。

我们来概览一下今天我要讲的内容。首先，我会简要介绍一下LLL算法。LLL是一个非常基础的算法，是我们已知唯一可用的算法。之所以我要简单介绍一下LLL算法，原因是这个算法是1982年被发现的，可以找到很多有关LLL的资料，大家可以阅读一下，这样大家对LLL算法的了解就跟我一样了。有一些人对LLL了解的更深入，比如实现LLL的工程师们。但是，需要花费很长的时间，才能知道如何对算法的各个方面进行优化。我今天只是简单介绍一下LLL，如果你想更深入地了解LLL，可以读Oded Regev的讲义，这是一个学习LLL非常好的资料。这个资料特别棒，里面包含了很多我所不知道的有关LLL的内容。不过我认为更重要的是，当你知道LLL可以做什么了以后，如何利用LLL攻击基于SIS问题或LWE问题的密码学系统呢？LLL和其他格归约算法在实验和实际使用中的性能又怎么样呢？我们会讲到有关LLL的理论证明，以及有关LLL的运行实验结果。

Oded Regev的课程讲义链接是：https://cims.nyu.edu/~regev/teaching/lattices_fall_2009/。

我认为这些内容非常重要，这也是我们设置参数所依赖的理论和实践依据。就像我昨天给大家展示的这张图片，我们基于格构造密码学系统的方法有如下两类：我们有SIS问题，我们有LWE问题。我们基于SIS构造Minicrypt，基于LWE构造Cryptomania。最近的一些研究成果显示，我们可以基于LWE构造更加高效的密码学方案。我不会讲这些内容，可能Chirs在他的讲座中会讲，我们拭目以待。但是如果我请大家仅凭直观感觉回答这样一个问题，我们应该怎么对格密码学进行密码学分析？如何基于问题的困难程度进行密码学分析？直观上看，你可能会说，我们已经知道，格密码学所依赖的困难问题都是最糟糕情况困难问题，我们来看看在最糟糕情况下，攻击算法的运行效率如何。不过这不是我们进行密码学分析的方法，原因有二。第一，我们很难知道在最糟糕情况实例下攻击算法的运行性能。我们如何找到这些最糟糕情况实例呢？在平均情况实例下进行密码学分析要简单得多。这也是为什么我们要讲解格归约算法的本质原因。攻击算法在平均情况困难下解决SIS和LWE问题的运行性能如何？归约算法能给我们什么结论呢？这些归约算法并不是毫无用途。这些归约算法告诉我们的是，这些问题确实是非常困难的，这从理论上来讲很棒，但这个问题并非到此为止了。在实际中，我们需要知道如何设置参数。对于这类密码学分析，归约算法的证明过程没法告诉你答案。这些归约算法告诉我们这些困难问题是正确的，但归约算法没有告诉我们，如何设置参数，使得所构造的密码学算法是安全的。这是密码学分析关心的问题，这也是密码学分析方法的核心作用。如何攻击这些困难问题？答案是LLL，或者类似的算法。

这就是LLL算法。一个格有很多可能的基。举例来说，有蓝色这样的基，也有绿色这样的基。直观上看，蓝色的基从某种程度上讲似乎更好一些。为什么蓝色基比绿色基好？蓝色基向量更短，所以直观上说，我们想要的是找一个短向量。

蓝色基还有什么其他的特点，使其显得较好，让蓝色基更能帮助我们观察到格的样子？两个基向量更正交一些。两个向量的夹角更大，这会帮助我们更好地观察格。向量夹角更大等价于Gram-Schmidt的正交化程度不会太小，所以在二维空间中，我们认为蓝色基具有更好的正交程度。这是其中一个绿色向量，而这是与这个绿色向量正交的部分，它比这个蓝色向量的正交程度小，而这也就意味着蓝色基比绿色基更好。

在n维空间中，LLL算法要做的是，让Gram-Schmidt基的正交程度最大化。随着维度的升高，正交程度会下降，但我们希望它不会下降的太快。这是格归约算法的目标，它要找一个基，使Gram-Schmidt向量正交程度不会下降的太快，这也就意味着基向量差不多是相互正交的。

这就是LLL归约基的样子，这实际上就是Gram-Schmidt分解。你有一个基B，可以写为Gram-Schmidt向量 的组合形式。B的第一个向量是 乘以1，第二个向量等于 乘以某个值，也就是 与 平行的部分，再加上 与 的正交部分。这些 是从Gram-Schmidt正交化过程中得来的。如果你不记得 是怎么来的，也没关系，只需要知道这里有 就好了。

我们的目标是得到一个Gram-Schmidt基，使其具有一些比较好的性质。我们能得到什么比较好的性质呢？这是LLL归约基所拥有的性质。所有的 都要小于1/2。我们后面会看到，很容易满足这个性质。接下来，还需要满足这样一个奇怪的特性。这个性质的大致意思是，得到的向量不能太短。但实际上这个性质的意思是这样的：把这两个不等式放在一起，所得到的结论是，第i+1个Gram-Schmidt向量不能比第i个向量小太多，这是LLL算法的一个重要性质。如果满足这个条件的话，我们可以很容易证明，在这个基中有一个短向量。当然，这个向量和最短向量相比有一个指数级的近似比例。

我们来证明一下，这个证明很简单，证明如下。如果我们得到的结果满足前面的条件，Gram-Schmidt基向量长度下降的不会太快，你就得到了这个不等式。我这里要用到一个结论，第一个Gram-Schmidt向量就是第一个格向量，所以你可以把不等式重写成这个样子，所以 ，其中i等于1到n。正如昨天Oded讲座中所讲到的，我们很容易证明，因为 的最小长度小于Gram-Schmidt向量中的最短向量，我们有 ，这就完成了证明。LLL的目标就是要得到满足这个条件的基，使得Gram-Schmidt正交部分的长度不要下降的太快。我只会用两页幻灯片讲解LLL算法，不会具体证明LLL的性质。

这就是LLL算法了，我们有一个基，我们用b表示。我把写成列向量形式，中间的是Gram-Schmidt正交基，用 表示，需要在正交基上乘以右边的矩阵，才能得到b。我们希望满足LLL归约基的两个性质。我们大概能看出怎样满足第一个性质，很容易满足这个性质。我们如何把任意 对应的基转换为另一个基，使得所有的 都小于0.5？看第二列第一行，看看这是不是小于0.5？估计比0.5大，你减去足够多次第一列，使得第二列第一行小于0.5。我们可以在不断地修改第二列第一行，不断减去第一个列向量。右边这是一个对角线全为1的上三角矩阵，这起到了重要的作用，很容易使得这些 都小于0.5。你也可以看到，在让这些 都小于0.5的过程中，我们没有改变Gram-Schmidt正交化结果，这些向量保持不变，正交部分保持不变，因为你做的只是减去一个与平面平行的平面。

当完成这一步以后，我们要做第二步，检查这些列向量的长度是不是下降的足够慢。如果 和 不满足第二个条件，该怎么办？我要把 和 换一下。这是证明的核心部分，我这里不会证明的。这意味着，每次进行交换后，我们都会更接近于得到一个好的基。每次进行交换，都会离好的基更近，而且接近比率是固定的。这里很难证明，可以读一下Oded讲义中的LLL算法部分。这个证明并不复杂，只是我没法直观地讲述这个证明过程。实际上我们没有足够的时间来直观地证明，为什么交换一下就可以帮助我们得到一个归约基。但这里的关键点是，一旦交换了两个向量，右边矩阵就全乱了，但是这会让我们更接近于得到归约基。我们重复进行这样的操作。

这就是LLL算法，关于LLL算法的内容就这些了，详细内容大家可以读一读证明，证明差不多有半页长，就这些了。这是一个非常简单，非常巧妙的算法，而且令人惊异的是，大概30年前 我们就基本上得到最好的算法了，后面学者们只是进行了一些优化和修改。如果你想进一步了解LLL，那我的讲解就不太够了。不过我认为，我们的目的并不是学习LLL算法，因为我们只有1.5个小时的时间。

现在我们来做一些有意思的事情。我们有了LLL算法，它有什么应用呢？由于一些历史原因，也不仅仅是历史原因，也是因为所有攻击算法用的都是同一个技术，我们只知道一种可以用LLL来证明安全的方法：取一个矩阵，把它向左翻转，向右翻转，再应用LLL算法。

我们来看看子集和。子集和问题是LLL算法的第一个应用场景。我们来解释一下子集和问题。本质上说，我们现在在用格来解决子集和问题，只不过我们的目的是证明安全性。

我们来看看子集和问题，子集和问题描述如下。有一个模数M，这个模数很大。有 中的随机值 ，这些 都是随机选取的。T是从 中随机选取的子集和。你有n个 ，有T，所有这些都是在模M下的。你的目的是找到 的一个子集，使得子集和模M下等于T。

举个例子，比如M等于49，这些是 ，这是T，那么满足条件的子集是什么？

这个问题有多难呢？我们有n个数， 到 ，以及一个目标值T。如果我告诉你T确实是 中某个随机选取子集的和，一个很明显的算法是把所有的 子集都试一遍。 一共有多少个可能的子集呢？ 个。所以这个问题的困难度依赖于n的大小。

为什么问题的困难度也依赖于M呢？这就不那么直观了。如果M非常小，如果模数非常小，存在一个简单的线性算法，可以在O(M)复杂度下解决这个问题。我想比较直观的算法复杂度是 ，如果使用动态规划的话。就能得到一个O(M)算法。

但还有个有趣的问题，n和M的关系也会影响问题的困难度，这就是引入LLL算法的地方了。实际上有意思的地方是，如果与n相比，M非常非常大，那么这个问题也是简单的。这挺有意思的，这是LLL的重要应用之一。

这是子集和问题的困难性，我们不会讲太多这方面的内容，我们只是了解一下。如果M非常小，大致为 ，我们可以在多项式时间内解决子集和问题。当M近似等于 时，子集和问题是最困难的。惊讶的是，如果M等于 ，问题又是多项式复杂度了。这里的2不是很重要，某个常数的 次方就行。左边是一般性生日攻击法，右边是格归约攻击法，我们要讲的是右边部分。我们要讲的是，当模数M比 大，如何解决子集和问题。

我们来用格解决子集和问题，我们用格归约算法解决子集和问题。我们有 到 ， ，其中 。我们要定义一个向量，把所有的 和 放进去。我们现在定义一个格，我们经常会用到这个技巧。我们有一些向量和数，我们要定义一个格。我们要用到格归约算法，所以我们需要一个格。这就是我们的格。这是一个在 中的格，其中a和y的点乘在模M下等于0。有点熟悉吧？我们昨天干过这个事，Chris昨天也干过这个事。这就是我们的格。

我们要注意到的一点是， 是一个格点，这个格点的范数小于 ，所以我们要用LLL算法找到这个x。很明显，我们要在这个格上使用LLL算法。

我把前面的部分重写了一下。这里我们不用 ，而用δ来表示长度的比例值。LLL会找到一个近似因子为 的短向量。不用管δ等于多少，如果你想的话，可以假设δ等于2。LLL可以找到一个向量，其范数小于 ，这小于 。因为我们知道我们要找的向量，其长度小于 ，LLL可以找到一个向量，其长度小于某个挺大的数乘以 。这很棒，如果格中不存在其他小于这个长度的向量，这个向量x就是唯一满足长度小于这个条件的格向量，LLL一定会找到这个向量。很好，但我们如何保证格中不存在更短的向量呢？有可能格不存在更短的向量吗？不一定，因为可能有整数倍x的向量，一定会存在这样的向量。不过没关系，如果得到了一个x的整数倍向量，我们可以把公共倍数除掉。如果我们得到的是3x，我们能看到每个坐标都是3的倍数，除以3，就得到向量x了。我们要找到一个好的向量，这个向量等于k乘以向量 ，这是一个好向量。我们希望能找到这样的向量，而且我们希望格中不存在其他的短向量了。

坏向量是 ，不用管k是多少，使得 。LLL可能找到的是这样的向量，这是LLL可能返回的合法向量，我们把这个长度表示为r，同时， ，意味着这是一个格向量。所以这个向量在格中，同时这个向量又很短。我们把等式重写一下，我没有做任何操作，我这里只把T写成了 的形式。我就是重写了一下，没做任何操作。接下来很重要，我前面已经说过，这不是一个x的整数倍向量，这不是好向量的整数倍，所以一定存在某个i，使得 ，因为如果对于所有的i， ，这就意味着 向量是 向量的整数倍，这就是个好向量了，我们除以k就可以了。这是坏向量的定义。我想证明的是，格中不存在这样的向量，或者证明当满足什么条件时，这样的向量不存在。

在格归约算法中，我们常用的技术就是设定参数，我们需要知道一些启发式结果。我们来定义某个球，这个球的半径是r，球中包含所有范数小于r的向量。我们可以证明下面这个关键的结果。从概率上可以这么做是由原因的，这也是为什么我们要求 是随机选取的。在格中，落在 中的向量的概率是多少呢？落在 中的向量都是坏向量。这个概率值实际上与 的选取有关。如果我们选取好了a，此时出现坏向量的概率是多少呢？如果M是质数，则概率值是1/M。如果M不是质数，也假定概率是1/M吧，除非括号中所有值都是0。如果这些都是0，那么对于所有M结果都成立。但是如果这些都是0，这就不是一个坏向量了。对于所有的i，模M都等于0，这就不是坏向量。

这就是为什么我们要求 是随机的原因。我们证明了对于任意元素，有1/M的概率得到一个坏的 向量。我们可以用联合上界确定M必须要达到多大，才能使得集合中的每一个元素中，得到一个坏向量的概率，也就是得到满足坏向量条件的a的概率很小。我们现在要用到联合上界了。我想证明的是，对于所有可能的 到 ，以及在这一集合中所有可能的 到 ，满足 乘以这些值，再求和后模M等于0。应用联合上界，这个值应该小于这个集合的子集个数，即 ，乘以这个集合中的元素个数，也就是这个集合的大小。这就是我们要求的条件，只要这个数值远远小于1，比如小于1除以 ，那么对于绝大多数随机选取的 ，LLL算法会找到这个短向量。

现在的问题是，这个集合的大小大概是多少？集合 有多大呢？为了解决这个问题，我们需要知道一个近似结果。球中有多少个点？在这个球中有多少个整数点？我们有个很棒的启发性结论。半径为r的球中，整数点的个数大致等于半径为r的球体体积。而球体体积大致等于这个数，半径的n次方乘以一个固定的比率值的n/2次方，而左边的这个固定比率值不太重要。这也提醒我们，半径至少要大于 ，因为如果半径没到 的话，那么球体没法覆盖到所有的整数点，这时候就很难分析球中格点的个数了，需要很多数学运算才能进行分析。但是对于密码学来说，这些都不重要，因为可以假定r至少为这个值。

这个公式在n为偶数下才成立。我计算得到过一个准确结果，那个结果在n为偶数时成立。不过这是个近似结果，对所有n都成立。

很好，现在我们知道了球体中点的个数，坏格向量的概率等于球体体积乘以 ，这个值要远远小于M，其中半径r等于这个值，即LLL所找到向量的长度。如果你把具体数带进去的话，就得到了这个结果， 。我们再带入其他的数，得到 ，这就是子集和问题的基础算法，以及相关的证明了。