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

演讲视频简介

我们继续更新2012年BIU密码学冬令营第04期的内容。第二部分主要介绍LLL算法在SIS问题和LWE问题中的应用，以及在实际中如何设置格密码学的参数。

实话实说，这部分内容的翻译还是相当艰辛的，很多讲解和解释已经涉及到了格密码学非常晦涩的内容。如果有翻译不正确的地方，还请知友们随时告知，万分感谢！

演讲视频信息

演讲视频字幕

我们来看看LLL在SIS问题中的应用。

这是SIS问题。给定一个随机矩阵A，找一个短向量s，任意范数定义下的短都可以，使得As等于0模q。后面会看到，因为某些技术原因，我们只考虑m不是很小的情况。m要大于2n，这就是实际系统中使用的参数，且q要大于m，这也是实际系统中使用的参数。所有我提到的关系都和当前使用的密码学参数相关，这里所用到的参数就是实际中使用的参数。

如何利用LLL寻找一个短向量呢？我们要使用相同的思想，我们要创建一个格，这个格在 上，格中的所有点均满足 。我们把A作为相等检测矩阵，昨天Chris也多次用到这个技巧，今天我们又用到这个技巧了。L(A)的最短向量是什么呢？这里要注意一下，n现在不再表示维度了，m是维度。根据Minkowski定理，我们很容易得到，最短向量长度小于 。

问题是，格的行列式等于多少？我们要求解格行列式的值。这个格的行列式是多少？大家有什么想法吗？我们要用到一个结论，如果L是一个整数格，那么行列式的大小等于 群中元素的个数。另一种等价的表述方法是，行列式的大小等于L的任意平行多面体中整数点的个数。我们首先可以证明，行列式最大为 ，原因是 ，对于任意的整数向量 和 ，如果 ，那么 和 在同一个陪集中。为什么？ 和 必然是 中的同一个元素。为什么？因为 在格中，而这就是相同陪集元素的定义。 属于格，因为 。

现在的问题是，如何证明格中至多有 个元素？如何证明行列式的值最多为 ？因为As的结果最多有 种可能，因为A是一个n乘m矩阵。现在我们可以称，如果A有n个线性无关列向量，那么行列式的值严格等于 ，原因是对于每一个陪集表示，对于 中的每一个y，一定存在一个x，使得Ax=y。为什么？是的，高斯消元。这就是为什么我们要求A有n个线性无关列向量的原因。这里我们就要用到m等于2n这个条件了，如果m=2n，则有很高的概率使得A拥有n个线性无关列向量。对于任意选取的A来说，有很高的概率满足这个条件。对于随机选择的A来说，行列式等于 。

很好，现在我们可以寻找最短向量了。根据Minkowski定理，我们知道，最短向量最长不会超过 。我们还知道，对于绝大多数A，行列式的值等于 。因此 最大为 。但这只是一个上界，只是一个上界而已。这个上界紧吗？大家觉得呢？这个上界没办法更紧了。这个界很紧，实际上与上确界仅差一个小常数。

我们现在要计算得到正交格的最短向量。我们有个 ，这还是一个球。我后面会讲到，因为我们这里要找到这个最短向量，LLL可以帮助我们找到短向量，所找到的向量与最短向量差一个近似比率，所以有必要知道，最短向量应该是什么？这里还有一个细节点，现在暂时不用管。我们有这个 ，这还是一个球。对于任意不满足模q等于0的s，对于所有的A，满足As=0的概率是 。看到了吗？方法是一样的。这里的 就是前面的1/M。现在，对于所有不满足模q等于0，且在 中的s，选择一个A，且满足 的概率小于 。我这里用了联合界，所以概率近似等于 。这就是m要比较大的原因，因为要除以 ，r大概需要等于这么大，才能让让结果远远小于1。这里和子集和问题的思想是一样的，所以我才要先讲子集和问题，子集和理解起来更简单。

所以对于绝大多数A，最短向量大于左边式子且小于右边式子。Chris认为这个结论不紧，尤其是当m比较大的时候，但我实际上主要是从密码学角度考虑的这个问题。正常来说，m和n的值应该很接近，可能m只比n大一点点。但是实验结果表明，算法实际运行结果接近左边的式子。也就是说，最短向量实际上和左边式子很接近。所以你就知道，下界是比较紧的。使用LLL，我们能找到一个长度为 乘以最短向量长度的向量，其长度大致等于左边的式子。所以如果你的问题是基于SIS的，且安全性依赖于寻找满足某个长度要求的短向量问题，那么这个长度最好要小于左边的式子。这就是我们设置参数的方法，这是设置参数的最好方法。后面我会告诉大家，基于实验结果应该设置的具体参数大小。一般来说，这就是我们设置参数的方法。

我这里要提醒大家注意一点。某些时候，破解一个密码学系统，比如哈希函数，一般都是在无穷大范数下破解。我们一般在无穷大范数下讨论问题。如果你可以破解某个方案，最好在无穷大范数下找一个短向量。而这个问题可能会更困难一些，因为我们还没有找到在无穷大范数下寻找最短向量的算法，我们只有在 范数下的算法。无穷大范数情况下的问题可能更困难一些，但不会困难太多。我们确实可以找到一个短向量，这个结果很好。但是在无穷大范数下，可能找不到这样的短向量，所以实际方案可能更安全一些。大家需要特别注意，证明中使用的是 范数。

讲到这里，有必要提到一点，我想Chris在他的讲座中也会提到的。有些时候，使用所有m个列向量反而没有意义，因为我们注意到，m会影响到最短向量的近似比率。这里m在指数上，m也会影响算法运行时间，不过是多项式级的。有时你可能想，如果你有一大堆列向量，可能你不想创建一个m维的格，得到这样一个近似比率。可能你想创建一个维度稍小的格，这个格的向量会稍微长一点，但因为你有这么一个近似算法，这个算法的输出结果依赖于格的维度，这就有意义了。有关这方面，我专门阅读了一个综述。这个综述是Daniele Micciancio和Oded Regev写的。他们在综述中解释了这个问题，告诉我们如何取一个比较优化的m值。过程不是很难，你估计认真看半个小时就能明白，如何取一个比较优化的m值了。你要做的只是把这两个条件都考虑进去，从而得到一个短向量。

现在我们来看看LWE问题。Chris昨天讲到了LWE问题，但大家举一下手，谁还记得Chris昨天讲过LWE问题？

这就是LWE问题。你有一个矩阵A，一个m乘n维矩阵，矩阵A乘以某个秘密s，加上e，等于b。你的目标是找到s的值。

判定问题和搜索问题等价。你有一个满足LWE分布的有效实例，其中e很小。你还有一个完全随机选取的实例，其中A和b都是随机选取的。

一种很好的解决LWE问题的方法是解决SIS问题。观察这个矩阵，实际上这就是把SIS中那个矩阵转了一下。昨天Chris已经讲过了，我们讲得快一些。使用LLL，我们可以找到这么长的一个向量，使得 ，这个结论是从SIS分析中得来的。

一旦你得到了一个v，满足 ，你就知道，如果b确实等于As+e，则 很小。

这是因为 ，而 也比较小，因为e比较小。如果b是均匀随机选取的，那么 也满足均匀分布。

现在你只需要做一个简单的计算。你知道 ，而这又小于SIS分析中得到的值乘以e的范数。这是v的范数，我们可以找得到。而这是e的范数。

这告诉我们，如果LWE问题中含有太小的噪声项时，如何解决LWE问题。如果你的密码学系统，其安全性依赖于错误项e，其中e远远小于模数q，这就出问题了。这就是我所说的意思，如果这个值小于q/2，就可以解决LWE问题。这就是解决LWE问题的方法了。

即使LWE的定义称，可以用任意多的采样值，但在实际中，在绝大多数应用场景中，你用不到那么多的采样值。对于密码学系统，你只能得到线性多个采样值，但采样值中内置了更大的噪声。前面的算法假定我们可以获得很多采样值，这样我们就可以找到一个短向量s，使得s乘以A等于0。但是如果我们没有那么多的采样值，我们就没法用这个算法了。至少我们可以进行一些的优化，我们可以选一个比较优化的m值，这样你会更可能找到一个最小的向量v。但是如果我们没法得到那么多采样值，我们可以用搜索-判定LWE归约算法来产生新的采样值，我们可以这么做，但有时候我们做不到。比如在理想格中，我们不知道这个方法能不能用。我们没法解决判定LWE问题，因为前面我们解决判定LWE问题的方法中，我们没有在求向量s，我们是通过归约算法寻找向量s，所以我们还是要重新解决判定问题。我们可以得到更多的采样值，重新解一遍，得到更多的采样值，再重新解一遍。我们要能得到最够多的采样值，才能让搜索LWE归约算法运作。但是很多时候我们做不到，我们只有有限个采样值。

这是一个可以直接解决LWE问题的方法，我们来看看这个方法，这是一个用较少采样值解决LWE问题的方法。我们有A乘以s加上e等于b，这是最小可能的情况了。我们假定e和s都比较小，如果s很大就没意义了。能看出为什么吗？因为如果s很大，那么噪声可以永远为0。e和s都要比较小，但正如昨天你们已经知道的，这等价于LWE问题。实际上，这种参数设置方法和现实中是对应的，有一些方案就是这么设置的参数。

我们接下来这么做。注意到，这可以写为 。可以进一步写为： 。这是什么？我们有了格，这个格的维度是2n+1。我们定义了格A'，其列向量的维度是2n+1。这个格要满足 。这和我们前面讲到的子集和例子特别像，且s和e有唯一解。

我不用再证明一次了，大家可以基于子集和问题自己证明一遍。你可以证明对于大多数A，坏向量的长度至少为...管它是什么值呢。如果这个值特别大，我们就可以解决LWE问题。

这里有一点要特别注意。我们有这些值，我们有前面举的那个例子。如果(s|e|-1)的范数小于这个值，你就可以解决LWE问题。如果所有向量的长度至少为这个数，LLL找到的向量就会很小。这时你运行LLL算法，你解决了LWE问题。但如果情况不是这样的呢？如果LLL找到的向量只是长了一点点呢？不管是理论还是实际，LLL得到的向量没在解决LWE的区间内。LLL得到的短向量比这个界稍微大了点。如果不看下一页幻灯片的话，你觉得会发生什么情况？

假定我们有一个中等长度的向量，或者有一个比较短的向量，但不是特别短，LLL算法没法找到一个特别短的向量，它做不到。但是有一个中等长度的向量，那么LLL算法找到的向量长度，与格中短向量的长度还有关系吗？直观上讲，好像还是有关系的。但是如果你深入思考一下的话，就会发现其实没关系。直观上，确实好像有关系。假设有一个向量的长度是5，有一个向量的长度是2，我们应该去找到那个更短的、长度为2的向量。但这并没有什么意义，因为这样的话，你就可以用LLL判断LWE实例有没有短向量了。即使未找到正确的短向量，LLL也能区分LWE包含一个短向量。所以如果LLL算法的输出与最短向量长度相关的话，你都不需要关心近似比率好到什么程度了，你直接可以说 LLL找到了一个短的向量。如果没有短向量，我根本就不应该找得到，因此我就不用再找了，你已经解决LWE问题了。

在密码学上，很幸运。在实际中，输出结果与最短向量的大小无关。算法或者找到短向量，或者结果就好像格中没有短向量一样。如果你认真思考一下的话，就会发现这好像也有道理。凭什么最短向量会影响到算法的输出结果呢？我的意思是的确存在一个短向量，但是我们能做到的就这些了，LLL甚至完全找不到另一个短向量，好像短向量根本不存在一样。那么为什么LLL的输出会有这种性质呢？这很重要。我们来看看实际情况。

实际情况是什么样的呢？这是Nicolas Gama和Phong Nguyen的成果。他们在2008年做了很多实验。我认为，现在人们是按照他们两个的成果来设置参数的。

正如我们前面看到的，有两类问题。第一类是存在最短向量问题，有点像SIS。第二类是存在唯一向量问题，有点像LWE问题，或者前面我们解决的子集和例子。在短向量问题中，我们给定一个矩阵A，要求你找到一个短向量s，使得As=0。我们没有内置任何秘密值，没有预先选过什么子集，这里面没有一个短的有些不寻常的向量。我们只需要找到一个短向量s。这类问题的特点是，s的范数比行列式值的1/m次方要大，因为这和Minkowshi给出的上界很接近，上界就是大于行列式值的1/m次方。

在另一类问题中，给你A和As模q，你想找到短向量s。这就是LWE问题，我们5分钟前刚讲过，这里s的范数要小于行列式的1/m次方，这是一个内置的向量。第二类问题是唯一短向量问题，我们要找到唯一的短向量s。

我们假定下一个最短向量是v，其长度不是s的倍数。实验表明，而实验结果没有超出我们的预估，找到s的困难程度与 相关。我们来讲讲为什么这个结论非常自然的原因。s是最短向量，v是第二个最短向量。v这是LLL可能找到的向量，s是我们希望得到的向量。我们令 ，即格中的第二个连续极小值除以第一个连续极小值。这就是α，只需要记住α的定义。

在短向量问题中，你要找一个向量s，使得As等于0模q，而格里面不存在非常短的向量，这和我们前面刚刚讨论的结果相关。我们要找的短向量和格中实际上的最短向量没有什么关系。这个结论就能解释LLL的实际效果了，内置短向量只与全局参数相关，只与格行列式的1/m次方相关。如果我们没有内置一个短向量的话，LLL找到的最短向量，和格中实际的最短向量没什么关系，或者说如果格中内置了一个短向量，但是没有那么短，那么被求向量和内置向量没什么关系。因此，我们令α等于你找到的向量s乘以这个行列式值，把这个参数嵌进去。短向量问题中，α等于||s||除以格的行列式。唯一短向量问题中，α等于λ_2除以||s||，或者λ_1除以||s||。

下面是论文给出的突破性工作，他们发现了下面的结论，这也是实际中我们设置参数的方法。这可能是你所问问题的答案，也就是参数要满足什么关系。左边，你需要计算行列式的值。如果安全性基于短向量问题，为设置参数，你需要计算行列式的值。如果安全性依赖于唯一最短向量问题，你需要计算你格λ_2的值。我们有下面的结论。如果要运行LLL解决困难问题，α可以为 ，其中m为维度。但肯定没人运行LLL，他们都运行比LLL更好的算法，这个算法叫做BKZ，这是LLL的改进算法，这时就变为了 。我们的推论如下。如果α等于1.007，方案应该是安全的。1.005的话，除非格归约方面有了重大突破，在可预见的将来，方案应该是不能被破解的。

这就是实际中设置参数的方法，就这些了，我们要知道的可能就这么一页幻灯片。如果你希望很难求解s，则一旦你计算得到||s||的范数，或者||s||本来就应该比较难找得到，例如||s||和方案依赖的困难问题相关，你只需要把等式中的这些数带进去，且保证α不能太大。

这些是参考文献。如果你想构造格密码学方案，强烈建议读一读Nicolas Gama和Phong Nguyen的这篇文章，以及Oded和Daniele的这篇综述。这些论文能告诉你在不同条件下该如何设置优化参数。如果你想了解LLL，请阅读Oded的讲义。

我们在例子中看看这个问题。这个α告诉你，攻击者可以找到什么长度的s。 等于s除以格的行列式，所以s等于α乘以行列式值。这是攻击者能找到的s值。所以你密码学系统的安全性，最好不要依赖于找满足这个长度要求的短向量问题上。

可能你想构造一个哈希函数，或者你想构造一个更短的签名方案，那可能需要其他的限制条件，需要在这些限制条件下构造方案。然后，你把这些参数嵌进去，看看是不是安全的。但我不认为我们可以把参数固定下来。如果你设计的是签名方案，那么q要等于这个，n是这个，m是这个，因为有时你会希望q很大，有时你会想让参数满足其他条件。举个例子，对于签名方案，如果q非常大也没什么关系。但在哈希函数中，你可能不希望q很大。具体参数的选取和你构造的方案相关。所以q和n的大小选取，并不是因为安全性的要求，而是一些其他的限制条件所要求的。我可以讲一些比较显然的结论，你总可以找到一个长度为q的向量，也就是(q,0,0,0,0)，所以你要保证这个向量不会带来安全问题，你的方案不会因为这个向量而遭到破解。但从安全角度，我们只关心这些关系。如果你想提高安全性，如果你想考虑其他一些情况，比如NTRU要让参数很小，或者要求0的个数很少，让1的个数很少，那你需要根据要求进一步设置参数了。只要选取的参数都是随机的，那么安全性方面只需要考虑这些就可以了。如果参数满足这些条件，方案就是安全的。