2012年BIU密码学冬令营-02-SIS归约-第2部分

密码学话题下的优秀回答者

演讲视频简介

我们继续带来2012年BIU密码学冬令营Lecture 02第二部分的讲座。有了第一部分的铺垫，第二部分重点讲解如何将SIVP归约为SIS问题。虽然对于密码学方案本身的构造没有太大关系，但这个归约过程非常巧妙，对格理论感兴趣的知友们可以深入了解一下。

当然了，我个人对于密码学构造更感兴趣，因此这部分内容并不是理解得非常深入。如果视频中有翻译错误的地方，还请专门研究此领域的知友们指正。

演讲视频信息

演讲视频字幕

我们开始吧。我们在午饭前讲到哪里了呢？我们证明了一个定理，这个定理对于归约算法来说非常重要。如果我们依高斯分布产生一个向量X，高斯分布的参数s为5乘以第n个极小值，就是格的连续极小值，也就是5乘以B的 $λ_n$ 值，那么X模B的统计距离与均匀随机分布非常接近。这就是我们需要的参数，我们需要5乘以B的λ_n值。如果我们取更大的参数，结果仍然是均匀随机的。当我们把s增大时，如果对于小s是均匀随机的，那么对于大s也是同样的结果。

这里我给出了图像，这里我们把s的值取的不那么大，得到的概率分布就是这样的。

随着s的值越来越大，最终会得到一个均匀随机的概率分布。

现在我们开始讲解归约算法。原始的归约算法是Ajtai提出的，这是一个非常漂亮的归约算法构造，而且这个归约算法开创了基于格的密码学。不只是因为归约算法所得到的结论，更多的是因为很多聪明的学者们开始对格感兴趣了，所以Glodwasser开始研究格，Goldreich开始研究格，他们的学生继续进行研究，所以Regev开始研究格。所以这个归约算法确实令很多学者开始对格感兴趣了，这是一个非常漂亮的归约算法。

我今天要给大家讲解的是Micciancio和Regev提出的归约算法，它们简化了Ajtai的原始归约算法。他们提出的归约算法非常直观，非常自然，他们使用了高斯分布。现在一般认为这是正确的归约算法，而且算法非常直观。

我们来看看这个算法。我们现在要把SIVP归约为SIS。如果你可以解决SIS问题，你也可以解决SIVP问题。我们开始吧。在二维空间中，这个图没什么太多其他的意义，我们以这个格为例讲解归约算法。但是你知道，我们已经能从这个格看到短向量了，不过假设看不到，好吗？归约算法要解决的基本问题如下。你有格的某个基，你想利用SIS算法，在格中找到一个更短的向量，这个向量也在给定基所在的格中。这就是我们要解决的问题。

我们来看看归约算法是如何工作的。我们假定你有了这么个格基，并且假定这个格基并不是特别好，即使看起来是个挺好的格基。不过这里我们假定这个格基不太好，很难用一页幻灯片展示一个不太好的格基，而且这么做本身也没什么意义。我们人为把空间划分成块，把空间用小一点的平行多面体划分一下，这样就把空间用小一点的平行多面体划分开了。这里我划分成了三份，但是一般来说要划分成O(n)份。我们把每一份都做个标记。从原点开始，原点标记为(0,0)，沿着横轴依次为0、1、2。到下一个格点，横轴重新标记为0。0、1、2，0、1、2。横轴和纵轴都这么标记，纵轴也这么标记。我们就人为地把空间划分成了这么个样子。

我们来观察一下。所有的格点都被标记为(0,0)，在n维空间下也是一样的。在n维空间下，所有的格点被标记为n个0。反过来也是一样的，只有标记为(0,0)的点才是格点。很简单，没问题。现在我们想利用一下SIS预言机。回忆一下SIS预言机可以做什么。给它n个向量，它可以找到这n个向量的一个短的线性组合，使得n个向量和模q等于0。在这个图上，q等于3。我们接下来做这么一件事，我们把算法重复m次，选择一个随机的格点，注意这有点像思想实验，实际上我们没法随机选择格点，先跟着我的思路走。随机选择一个格点，我选择了这个格点，就这个了。把它标记成红色，选择这个格点，这是一个随机选择的格点，然后以这个格点为中心，进行高斯分布采样，采样出一个点。这里我选择了这个点，然后进行高斯采样，输出了一个和格点距离比较近…这个高斯分布要按照某个标准差来选取，所以最后我们得到这么一个点。我们再随机选择一个格点，并且依高斯分布再采样另一个点，这个点在这里。我们再随机选择一个格点，再依高斯分布采样一个点，这个点在这里。依高斯分布采样的点不一定落在网格上，但我们假定可以让它在网格上，比如舍入一下，让它落在网格上。

现在我们假设高斯采样的点也落在网格上。再继续往下进行前，我们需要一个背景知识。我们在这里需要用一下前面讲到的一个定理，也就是所有的采样点在 $Z_q^n$ 下都是均匀随机分布的。能看出原因吗？这很重要，q等于3，为什么采样点在 $Z_q^n$ 下是均匀随机分布的？完全正确，我们把高斯分布参数选为比5 $λ_n$ 更大的值，这意味着这些点在平行多面体中是均匀随机分布的。如果你把这些点模平行多面体，这些点在平行多面体中是均匀随机分布的，但这也等价于选择一个随机的格点，然后依高斯分布选一个偏移量。所以只要标准差足够大，这些点的分布在平行多面体中就是均匀随机的。所以这些点的分布在平行多面体中式均匀随机的，但是平行多面体就在 $Z_q^n$ 上，这没问题。你不知道 $λ_n$ 的值是多少，但是只要你选取一个标准差，并且标准差大于 $λ_n$ ，那么归约算法就可以运行了。所以这里你不需要知道 $λ_n$ 的值，你只需要选一个比 $λ_n$ 值大的标准差就可以了。总有一个时刻，归约算法会停止运行，你就可以停下来了，算法就得不到正确的结果了。所以这个算法不可能永远执行下去，但是只要标准差大于 $λ_n$ ，你就可以继续执行算法。

我们留意下第三个点。我们希望按照高斯分布采样，但这个点实际上离下面这个点更近。但这是有可能发生的，因为高斯分布的半径取的是 $λ_n$ ，所以所取点距离的期望是 $λ_n\cdot \sqrt{n}$ ，所以这没问题，很可能采样得到的点离另一个点的距离更近，而不是离高斯采样时的中心点离得更近。这实际上对归约算法来说非常重要。所以我想要达到的目的是，得到一个向量，这个向量的长度比已有的向量都短，比U的向量都短。

我现在要做的是把这些在 $Z_q^n$ 中采样的点发给SIS预言机，但我不给它格的采样点，我给它采样点的坐标。这个点的坐标是(0,1)，这个点是(2,2)，这个点是(0,1)。我把这些向量发送给SIS预言机。然后我告诉预言机，找这些点的短线性组合，使得和在模q下为0。所以这是我的采样点，这是我们创造的平均情况问题。预言机开始工作，输出 $z_1、\ldots、z_n$ ，它们都在 $\{-1,0,1\}$ 之中，或者说它们都很小，z是一个短向量，但满足线性组合模q等于0。

好的，我将用这个答案来找到一个更短的向量，也就是找到一个比已有向量都更短的向量。还记得我们前面选了一个抗碰撞哈希函数吗？所以一旦存在碰撞，你把两个碰撞值相减，结果就等于0。所以只要定义域选的比值域大，这种情况就一定会发生。所以我们要求2的m次方要大于q的n次方，而2的m次方确实大于q的n次方。所以我们把采样点发送给了预言机，预言机回复了结果，我们可以用这个结果做些事情了。

我们把这个红色的点称为 $v_i$ ，这是个格点。黄色的点，我们叫它 $s_i$ ，这些点不是格点，这些点与 $a_i$ 相关，我们是把 $a_i$ 发送给了SIS预言机。这里还有个 $r_i$ ， $r_i$ 等于 $v_i$ 到 $s_i$ 的距离。这个距离与高斯分布的半径相关，所以这些 $r_i$ 近似等于 $λ_n\cdot \sqrt{n}$ 。这是高斯分布的标准差，也就是 $r_i$ 的长度期望。

我们有下面的结论。我们知道 $s_1z_1+\ldots+s_mz_m$ 是一个格向量，为什么？它模q等于0。正如我前面讲到的，任何等于0的向量都是格向量，所以这是个格向量。这也是一个格向量，为什么？这是从定义来的。现在这也是个向量，我只是把括号给打开了而已。因此，这个部分一定也是个格向量，为什么？这个结论不那么直观。为什么如果这是个格向量的话，最下面的这部分也是格向量？因为这个部分是个格向量，因此一个格向量加上某个向量还是格向量，那么这个向量本身也必须是格向量，所以这也是个格向量。 $a_i$ 是 $s_i$ 在网格中的序号表示， $s_i$ 是黄色的点，这个 $s_i$ 所对应的 $a_i$ 是1。 $r_i$ 是什么？ $r_i$ 是 $v_i$ 到 $s_i$ 的距离，是真实的距离，是几何距离，是格点到我生成的 $s_i$ 点的距离。

从SIS预言机的回复中，我得到了 $s_i$ 的一个短线性组合，将 $s_i$ 组合成了一个格点。因为SIS预言机的答案满足 $a_iz_i=0$ ，因此我知道 $s_i$ 的线性组合一定是一个格点。我们就直接用SIS预言机的结果，也得到了 $r_i$ 的一个线性组合，所以 $r_1\cdot z_1+r_2 \cdot z_2 + r_3 \cdot z_3$ 一定也是一个格点。 $v_i$ 是随机的其实没有什么太多的意义。你可以随机产生一个格点，这只是模平行多面体的一种表示方法。我们不用陪集来表示某个特定的点，不用群来表示某个特定的点，我们在整个陪集上表示。所以如果你相信我可以随机采样 $v_i$ 的话，我们相信可以做到，你可以在整个空间中采样格点。我用到 $v_i$ 是随机点的地方是，我要求黄色点在整个空间中是均匀随机分布的。因此，黄色点在 $Z_q^n$ 中也是均匀随机分布的。但在现实世界中，我们没法随机选择一个 $v_i$ 。所以，你需要选择在群中表示点，表示的结果是0，所以这也是一个格点。

所以我们得知 $r_1z_1+\ldots+r_mz_m$ 也是一个格向量，我们基本证明完了， $r_i$ 都很小，这正是我们所需要的。

大家记得我在刚开始介绍高斯分布的时候说过，假设你想得到一个模10、模9、模8都均匀随机的概率分布，你只能把采样间隔设置到 $2^n$ 乘以各个间隔的长度，但其实你只是想找到一个短向量而已，这就是我们用高斯分布的原因。你希望用高斯，希望用某个分布来得到一个小的元素，并且这个元素模某个区域后是均匀随机分布的。这些就是 $r_i$ 了， $r_i$ 都很小， $z_i$ 也都很小，所以 $r_iz_i$ 也是个短的格向量。这个向量有多短呢？ $r_i$ 近似等于 $5\sqrt{n} \cdot λ_n$ ，一共要加上m个 $r_i$ 。当加上m个 $r_i$ 后，你可能会说，范数应该是 $m \sqrt{n} \cdot λ_n$ 。我们可以得到更小的范数，因为所加的数都是随机数，所以一部分值会被消去，所以相加的结果近似等于根号m乘以 $r_i$ 的长度，所以等于 $\sqrt{m} \cdot \sqrt{n} \cdot λ_n$ ，所以等于 $n \cdot λ_n$ 。如果归约算法可以正确执行，可以保证你能得到一个格向量，且向量的长度等于 $\sqrt{m} \cdot \sqrt{n} \cdot λ_n$ ， $\sqrt{m} \approx \sqrt{n}$ ，所以是n，这就是参数n的来源，这就是归约算法的基本思想了。

这里有很多技术细节，我们应该已经都接触到这些细节了。首先，可能没办法依均匀随机分布采样格点，这也就是为什么在证明中，我们在 $R^n$ 模L下操作。

还有个更有挑战的技术细节，如果和为0怎么办？那得到的结果就没用了，你得到了一个0向量。这非常重要，而且这是最难证明的一个技术细节。在论文中，证明这个技术细节花费的篇幅是最大的。可以证明，和在很高的概率下不为0，原因是给定 $s_i$ ，有很多可能的 $r_i$ ，所以这个技术细节的证明与我前面问的一个问题相关。还记得这个点与这个格点的距离实际上很近，对吗？这在归约算法中起到了重要作用。因为SIS预言机没办法指出 $a_i$ 是从哪个格点中得来的，所以它没法指出 $r_i$ 是多少。如果SIS预言机想要欺骗归约算法，回复一个0向量，它做不到，因为它不知道r的真正值。所以在未知 $r_i$ 的情况下，它没法返回一个0向量。因此，可以证明在不可忽略的概率下，回复的向量和不为0。

第三个问题是，高斯采样点不一定在网格上，但是我们可以利用一些确定性算法对点进行舍入操作，把它移到网格上。但这里要注意舍入时会带来误差，需要在点上加上某个长度，才能移动到网格上。但这不会有什么影响，我们还可以做得更好，比如直接在网格上采样点。我想Chirs会在周一的时候讲到这个技术，这个技术是离散高斯采样。从概念上说这有点难理解，但你确实有方法得到网格上的点。

2012年BIU密码学冬令营-02-SIS归约-第2部分

2012年BIU密码学冬令营-02-SIS归约-第2部分

演讲视频简介

演讲视频信息

演讲视频字幕

Recommend

Personointi ja sisällönhallintajärjestelmät

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

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

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

2012年BIU密码学冬令营-03-Learning With Errors-第1部分

2012年BIU密码学冬令营-02-SIS归约-第1部分

2012年BIU密码学冬令营-01-格简介-第3部分

2012年BIU密码学冬令营-03-Learning With Errors-第2部分

2012年BIU密码学冬令营-01-格简介-第2部分

2012年BIU密码学冬令营-01-格简介-第1部分

About Joyk