格（Lattice）学习笔记之九：Ring-SIS与Ideal Lattice

Original 东泽安比技术社区 2020-08-25 12:30

本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。

回顾：从SIS到Ring-SIS

在之前的笔记中有所提到从SIS到Ring-SIS的转变，现在我们回顾一下。

由SIS构造的哈希函数具有单向且Collision Resistant的特性。但是缺点很明显：因为SIS问题矩阵的大小的原因，导致了计算这个哈希函数的计算复杂度达到了之高。

然而，当我们看SIS这个问题的安全性的时候，却发现我们只要靠猜，就能在的时间内就能猜出来。这样一来其实这个哈希函数并没有什么太大的优势：计算复杂度太高，从而导致破解复杂度与计算复杂度的比例过低。

理论上我们需要一个可以快速验算（复杂度），并且破解难度保持相等（复杂度）的一个哈希函数。

之前的笔记中提到的一个尝试就是把矩阵横向切成份，然后每一份都是一个正方形的等宽矩阵。随后，我们赋予这个等宽矩阵一个特殊的构造：旋转矩阵。举个例子，如果：

这样一来，我们只需要记住向量的值，就可以重现整个旋转矩阵了，等于是我们把原本的压缩到了的大小。

Z[X]/(Xⁿ-1)结构的多项式环

之前的笔记也有所提到过，像上文中展示的旋转矩阵其实可以表示为：

其中表示为向量中的第位。

我们用这么一个集合来表示所有的阶向量可以组成的旋转矩阵集合。仔细观察这个集合可以发现，这个集合中的元素之间相互加减，甚至相乘之后都可以得到同样的集合元素，并且具有分配律，即：

加法性质很好理解，因为我们只需要把上述的表达式展开，代入进的值，再把各项系数相加就行了。乘法性质稍微tricky一点：我们观察发现，所以我们把两个旋转矩阵相乘，大于等于阶的可以直接约掉阶，也就是说最后得到的表达式一定是由组成的。而我们的旋转矩阵就是这么定义的。

总的来说，就是说这么一个集合不仅closed under addition，并且也closed under commutative multiplication，所以是一个环（Ring）。

仔细观察的话，上面描述的循环矩阵的表达式和的阶多项式非常相似。具体地说，与多项式环是同构的（isomorphic）。在这个多项式环中，加法和普通的加法一样，乘法在超过阶的时候有所变化：

这和我们上面的的定义是完美吻合的，只要超出阶，就退回到1重新开始。

即然多项式环可以完美的表达循环矩阵集合，我们也就没有必要一直拖着个循环矩阵到处走了。我们可以把一个循环矩阵用多项式环中的一个阶的元素来表示。紧接着，我们可以把原本的矩阵（拆分成了个循环矩阵），分别用来代替。其中代表了多项式每一项系数都在的集合中。

同理，我们的输入短向量也变成了一组短的多项式元素。这样整个哈希函数就变成了：

在之前的文章中也有所提到过，如果我们有多个多项式相乘，我们可以在的时间内计算完，并且这里的加法是高度并行的。这比起之前的的计算速度要快多了。

Ring-SIS问题回顾

根据上面基于多项式环的哈希函数，我们正式定义一下Ring-SIS：我们拥有一共个随机生成的多项式，目标是输入一组系数不全部为0的多项式并且使得：

之前在学习SIS的时候，我们知道如果可以找到一组SIS OWF的Collision，那么就等于找到了SIS问题的解。在Ring-SIS中也一样，如果我们可以成功的找到多项式环中的哈希函数的Collision，那么我们也能解决对应的Ring-SIS问题了。

可惜的是，这个多项式环下的哈希函数，虽然满足单向性（Micciancio07），但是并不是Collision Resistant的。也就是说，在下的Ring-SIS问题是简单的。

在之前的文章中，我们在循环矩阵的表达方式下Ring-SIS的解（把设置成全1，然后微调）。这一次，我们来看看在多项式环的表达方式中，如何证明这个环下Ring-SIS的安全性并不高。这里注意，证明安全性的关键在于多项式环的特征多项式可以被约分为：

首先，我们先假设为每项系数都为1的多项式：

根据我们上面描述的约分关系，我们发现。这个关系至关重要。

随后回到我们的Ring-SIS问题上来，问题会给我们一共个多项式，我们需要得到一共个短的多项式，这两组多项式的依次相乘加起来等于0。

解决的方式非常简单，我们直接忽略掉除了以外的所有其他个多项式。同理，我们把这些解的部分都忽略掉，只留下。随后，我们把设置为刚刚定义的。这样一来，只要我们的Ring-SIS问题就变成了：

这也就是说，只要，那么我们就找到了Ring-SIS的问题的解啦。这个解就是在的后面加个全0的多项式。

接下来我们看看，到底在什么情况下，会等于0呢？首先最trivial的case就是当为0的时候，不过这个情况我们不考虑，因为是随机系数的多项式。那么另一个情况就是当是的倍数的时候，即，那么我们相乘就会得到：

这也就是说，只要是的倍数，那么我们只要盲猜就可以猜中Ring-SIS问题正确的解。那么由于这里是的系数是随机生成的，正好生成到的倍数的可能性多大呢？

我们首先观察所有的倍数是什么样子：

我们发现，所有倍数的多项式都具有一个很特殊的属性：多项式每一项的系数加起来最后总和等于0！

由于Ring-SIS是在的多项式环上进行操作的，即每一项的系数都在以内，那么我们可以复现一下随机生成一个环中的多项式的过程：

首先，我们随机选择中的一个数字，使其成为多项式中第一项的系数。
随后，我们用同样的方法，依次随机的生成，即一直到第项的系数。
现在最后只剩下最后的一项系数没有生成了，即第项。这个时候我们发现，因为前面项已经确定了，那么如果我们希望这个多项式是的倍数，那么它一定要满足：
因为我们所有的系数都在中，所以我们随机生成的话就是在个元素中随机的选择一个元素。那么这样随机的选中的可能性就是了。

这也就是说，任意的给定一个如上描述的Ring-SIS问题，我们如果盲猜作为解的话，竟然会有的几率会猜对！

这个概率对于Ring-SIS的安全性来说实在是太大了。这也就是说，如果我们想要达到SIS问题中我们得到的的安全性（复杂度）的话，我们需要把的大小设置为才行。在如此大的q的情况下，就算我们计算Ring-SIS的哈希函数可以通过FFT来加快速度，最后得到的时间复杂度甚至大于了原本的SIS的时间复杂度。

Z[X]/(Xⁿ+1)结构的多项式环

因为之前我们用的环的特征多项式可以被约分，所以导致用原本的环构造出的Ring-SIS问题非常好破解。在之前的文章里也提到了解决方案：使用一个特征多项式不能被约分的环来代替。

这个新的多项式环，就是。在这个环下的运算和之前大致相同，唯一不同的是临近阶时的乘法规则：

同理，代表了这个环的循环矩阵中的为：

这个新的环的安全性在于特征多项式的特殊属性。当是2的幂的时候，这个多项式又被称作Cyclotomic Polynomial（分圆多项式），而这个多项式是无法被约分的。所以在这个多项式环中，我们上面描述的破解Ring-SIS的方法就无效了。

Ideal Lattice（理想格）

接下来说一说Ideal Lattice的概念。

在环论中，有一类比较特殊的集合叫做理想（Ideal）。假如我们在一个环中，那么一个理想就是环的一部分。这个理想有几个特性：

首先，这个集合在加法空间内是封闭的（closed under addition），即任意两个理想中的元素相加或者相减之后也会得到一个理想元素：。
其次，理想中的元素与环中的元素在乘法空间内是封闭的（closed under multiplication），即一个环中的元素和一个理想中的元素相乘，最后还会得到理想中的元素：。

在我们的应用场景中，是一个阶多项式组成的多项式环。这也就是说，我们可以很简单的把一个中的元素映射到中——只需要把每一个系数作为一个维度就好了。举个例子：

解决了之后，我们来看。这里我们要用来表示之前描述的这么一个特殊的多项式环。我们可以把看做一个特殊的Lattice ，并且在之前描述过的循环矩阵的变换矩阵的运算下是封闭的。换句话来说，如果，那么。展开来看的话就是：

我们一般称这样的构造为Anti-cyclic Lattice。反之，如果我们用的是前面特征多项式对应的线性变换的话，那么得到的Lattice叫做Cyclic Lattice。这就是所谓的理想格了。

理想格其实是一种很奇怪的格结构。假如我们从理想格中选出任意一个非0的向量，我们可以依次对这个向量施加线性变换，并且获得个线性独立的向量：

我们观察发现，的Determinant是1，代表这个线性变换是可以维持原本向量的长度的，这也就是说，这些线性独立的向量的长度全部相等：

这代表什么呢？这代表理想格中的最短向量问题SVP与最短独立向量问题SIVP是一样的！这是因为只要存在一个最短的向量，那么我们就可以通过叠加线性变换获得其他的个独立的等长向量，这也就代表了。这样一来，在理想格中，有一部分原本的格的假设变得不同了，原本在普通的格中我们认为困难的问题，在理想格中可能很容易解决，或者难以证明难度。

理想格难题与Ring-SIS的规约

我们之前学到过，给定一个SIVP问题，我们可以规约到SIS问题，即我们可以把一个SIVP的难题“包装”成一个SIS问题，所以解决了SIS问题的话，我们也就获得了SIVP问题的解。这样的规约（reduction）直接证明了SIS问题的安全性。

我们还学到过，给定一个worst case的SIS问题，我们可以规约到average case的SIS问题，即如果能解决平均难度的SIS，就可以解决最难的SIS问题。这样的reduction证明了所有SIS问题的范畴中问题的难度分布较为集中，不会有特别简单或者特别难的。

同理，学习了Ring-SIS和Ideal Lattice之后，我们能否把Ideal Lattice下的SVP问题，即IdealSVP规约到Ring-SIS问题上呢？

答案是还不确定。目前这还是一个Open Problem，没有很有效的把IdealSVP转换为Ring-SIS的方法。这主要是因为Ring-SIS并不是纯粹的一个理想格问题，因为它的解是这么一个多项式构成的向量，而并不只是一个理想格元素。

所以现在格密码圈对于Ring-SIS的看法褒贬不一。一部分的人认为Ring-SIS可以很有效的提高格密码的运算效率，所以提倡它的普及应用。但是另一部分人认为Ring-SIS的难度规约还没有完成，所以不像SIS、LWE一样，我们不能完全的相信它的安全性。

不过密码学就是这样，有很多情怀的因素在里面。目前主流的同态加密库如HELib、TFHE等等都是使用多项式环来进行优化计算。

本文取材于Vinod Vaikuntanathan的讲义。讲义本身取材于Noah Stephens-Davidowitz的笔记。

封面图来自unsplash，作者Sharad Bhat

往期回顾

格（Lattice）学习笔记之一：历史与基本概念

格（Lattice）学习笔记之二：计算问题