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

微信扫一扫,分享到朋友圈

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的个数很少,那你需要根据要求进一步设置参数了。只要选取的参数都是随机的,那么安全性方面只需要考虑这些就可以了。如果参数满足这些条件,方案就是安全的。

微信扫一扫,分享到朋友圈

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

噱头再多,也看不下去!

上一篇

Java8线程池ThreadPoolExecutor底层原理及其源码解析

下一篇

你也可能喜欢

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

长按储存图像,分享给朋友