Lattice学习笔记09：Ring-SIS与Ideal Lattice
本文取材于Vinod Vaikuntanathan的讲义。讲义本身取材于Noah Stephens-Davidowitz的笔记。
回顾：从SIS到Ring-SIS
在之前的笔记中有所提到从SIS到Ring-SIS的转变，现在我们回顾一下。 $$ h_\mathbf{A}(\mathbf{e}) = f_\mathbf{A}(\mathbf{e}) = \mathbf{Ae} \text{ mod }q $$ 由SIS构造的哈希函数$ h_\mathbf{A} $具有单向且Collision Resistant的特性。但是缺点很明显：因为SIS问题矩阵$ \mathbf{A} \in \mathbb{Z}_q^{n \times m} $的大小的原因，导致了计算这个哈希函数的计算复杂度达到了$ O(nm \log{q}) \approx O(n^2) $之高。
然而，当我们看SIS这个问题的安全性的时候，却发现我们只要靠猜，就能在$ 2^{O(m)} \approx 2^{O(n)} $的时间内就能猜出来。这样一来其实这个哈希函数并没有什么太大的优势：计算复杂度太高，从而导致破解复杂度与计算复杂度的比例过低。
理论上我们需要一个可以快速验算（$ \widetilde{O}(m) $复杂度），并且破解难度保持相等（$ 2^{\widetilde{O}(m)} $复杂度）的一个哈希函数。
之前的笔记中提到的一个尝试就是把矩阵$ \mathbf{A} $横向切成$ l = m/n $份，然后每一份都是一个正方形的等宽矩阵。随后，我们赋予这个等宽矩阵一个特殊的构造：旋转矩阵$ Rot(\mathbf{a}) $。举个例子，如果$ n = 4 $： $$ \mathbf{a} = \begin{bmatrix}1&8&3&4\end{bmatrix}^T\ Rot(\mathbf{a}) =\begin{bmatrix} 1&4&3&8\ 8&1&4&3\ 3&8&1&4\ 4&3&8&1 \end{bmatrix} $$ 这样一来，我们只需要记住向量$ \mathbf{a} $的值，就可以重现整个旋转矩阵了，等于是我们把原本的$ \mathbf{A} $压缩到了$ \frac{1}{n} $的大小。
$ \mathbb{Z}[X]/(X^n-1) $结构的多项式环
之前的笔记也有所提到过，像上文中展示的旋转矩阵$ Rot(\mathbf{a}) $其实可以表示为： $$ Rot(\mathbf{a}) = a_1I+a_2X+a_3X^2+a_4X^3\ X = \begin{bmatrix} 0&0&0&1\ 1&0&0&0\ 0&1&0&0\ 0&0&1&0 \end{bmatrix} $$ 其中$ a_i $表示为$ \mathbf{a} $向量中的第$ i $位。
我们用$ \widetilde{R} = {Rot(\mathbf{a}) : \mathbf{a} \in \mathbb{Z}^n} $这么一个集合来表示所有的$ n $阶向量可以组成的旋转矩阵集合。仔细观察这个集合可以发现，这个集合中的元素之间相互加减，甚至相乘之后都可以得到同样的集合元素，并且具有分配律，即： $$ a, b \in \widetilde{R}\ a + b = b + a \in \widetilde{R}\ a \times b = b \times a \in \widetilde{R} $$ 加法性质很好理解，因为我们只需要把上述$ Rot(\cdot) $的表达式展开，代入进$ a, b $的值，再把各项系数相加就行了。乘法性质稍微tricky一点：我们观察发现$ X^n = I $，所以我们把两个旋转矩阵相乘，大于等于$ n $阶的$ X $可以直接约掉$ n $阶，也就是说最后得到的表达式一定是由$ I, X, X^2, \dots, X^{n-1} $组成的。而我们的旋转矩阵就是这么定义的。
总的来说，就是说$ \widetilde{R} $这么一个集合不仅closed under addition，并且也closed under commutative multiplication，所以$ \widetilde{R} $是一个环（Ring）。
仔细观察的话，上面描述的循环矩阵的表达式和$ n-1 $的阶多项式非常相似。具体地说，$ \widetilde{R} $与多项式环$ R = \mathbb{Z}[X]/(X^n - 1) $是同构的（isomorphic）。在这个多项式环中，加法和普通的加法一样，乘法在超过$ n-1 $阶的时候有所变化： $$ x \cdot x^i = \begin{cases} x^{i+1} & i < n-1\ 1 & i = n-1 \end{cases} $$ 这和我们上面的$ X^n = I $的定义是完美吻合的，只要超出$ n-1 $阶，就退回到1重新开始。
即然多项式环可以完美的表达循环矩阵集合，我们也就没有必要一直拖着个循环矩阵到处走了。我们可以把一个循环矩阵$ Rot(\mathbf{a}) \in \widetilde{R} $用多项式环中的一个$ n-1 $阶的元素$ a \in R $来表示。紧接着，我们可以把原本的矩阵$ \mathbf{A} $（拆分成了$ l $个循环矩阵），分别用$ (a_1, \dots, a_l)^T \in R^l_{[q]} $来代替。其中$ R_{[q]} $代表了多项式每一项系数都在$ [q] = {n:\lvert n \rvert < q} $的集合中。
同理，我们的输入短向量$ e $也变成了一组短的多项式元素$ (e_1, \dots, e_l)^T \in R^l_{{0, 1}} $。这样整个哈希函数就变成了： $$ h_{a_1, \dots, a_l}(e_1, \dots, e_l) = a_1e_1 + \dots + a_le_l \text{ mod }qR $$ 在之前的文章中也有所提到过，如果我们有多个多项式相乘，我们可以在$ O(n \log(nq)) $的时间内计算完，并且这里的加法是高度并行的。这比起之前的$ O(n^2) $的计算速度要快多了。
Ring-SIS问题回顾
根据上面基于多项式环的哈希函数，我们正式定义一下Ring-SIS：我们拥有$ a_1, \dots, a_l \in R_{[q]} $一共$ l $个随机生成的多项式，目标是输入一组系数不全部为0的多项式$ e_1, \dots, e_l \in R_{{-1, 0, 1}} $并且使得： $$ a_1e_1 + \dots + a_le_l = 0 \text{ mod }qR $$ 之前在学习SIS的时候，我们知道如果可以找到一组SIS OWF的Collision，那么就等于找到了SIS问题的解。在Ring-SIS中也一样，如果我们可以成功的找到多项式环中的哈希函数的Collision，那么我们也能解决对应的Ring-SIS问题了。
可惜的是，$ R = \mathbb{Z}[X]/(X^n - 1) $这个多项式环下的哈希函数，虽然满足单向性（Micciancio07），但是并不是Collision Resistant的。也就是说，在$ R $下的Ring-SIS问题是简单的。
在之前的文章中，我们在循环矩阵的表达方式下Ring-SIS的解（把$ \mathbf{e} $设置成全1，然后微调）。这一次，我们来看看在多项式环的表达方式中，如何证明$ R $这个环下Ring-SIS的安全性并不高。这里注意，证明安全性的关键在于多项式环的特征多项式$ x^n - 1 $可以被约分为： $$ x^n - 1 = (x-1)(1 + x + x^2 + \dots + x^{n-1}) $$ 首先，我们先假设$ \tilde{e} $为每项系数都为1的多项式： $$ \tilde{e} = 1 + x + x^2 + \dots + x^{n-1} \in \mathbb{Z}[x]/(x^n-1) $$ 根据我们上面描述的约分关系，我们发现$ (x-1)\tilde{e} = x^n - 1 = 0 $。这个关系至关重要。
随后回到我们的Ring-SIS问题上来，问题会给我们$ a_1, \dots, a_l $一共$ l $个多项式，我们需要得到$ e_1, \dots, e_l $一共$ l $个短的多项式，这两组多项式的依次相乘加起来等于0。
解决的方式非常简单，我们直接忽略掉除了$ a_1 $以外的所有其他$ l-1 $个多项式。同理，我们把$ e_2, \dots, e_{l-1} $这些解的部分都忽略掉，只留下$ e_1 $。随后，我们把$ e_1 $设置为刚刚定义的$ \tilde{e} $。这样一来，只要我们的Ring-SIS问题就变成了： $$ h_{a_1, \dots, a_l}(\tilde{e}, 0, \dots, 0) = a_1 \tilde{e} \text{ mod }qR $$ 这也就是说，只要$ a_1 \tilde{e} = 0 \text{ mod }qR $，那么我们就找到了Ring-SIS的问题的解啦。这个解就是在$ \tilde{e} $的后面加$ l-1 $个全0的多项式。
接下来我们看看，到底在什么情况下，$ a_1 \tilde{e} $会等于0呢？首先最trivial的case就是当$ a_1 $为0的时候，不过这个情况我们不考虑，因为$ a_1 $是随机系数的多项式。那么另一个情况就是当$ a_1 $是$ (x-1) $的倍数的时候，即$ \exists a’ \in qR : a_1 = (x-1)a’ $，那么我们相乘就会得到： $$ a_1 \tilde{e} = a’(x-1)\tilde{e} = 0 \text{ mod }qR $$ 这也就是说，只要$ a_1 $是$ (x-1) $的倍数，那么我们只要盲猜$ \tilde{e} $就可以猜中Ring-SIS问题正确的解。那么由于这里$ a_1 $是的系数是随机生成的，正好生成到$ (x-1) $的倍数的可能性多大呢？
我们首先观察所有$ (x-1) $的倍数是什么样子： $$ (x-1) \cdot k = kx - k\ (x-1) \cdot x = x^2 - x\ (x-1) \cdot (x + k) = x^2 - x + kx -k\ $$ 我们发现，所有$ (x-1) $倍数的多项式都具有一个很特殊的属性：多项式每一项的系数加起来最后总和等于0！
由于Ring-SIS是在$ qR $的多项式环上进行操作的，即每一项的系数都在$ q $以内，那么我们可以复现一下随机生成一个$ qR $环中的多项式的过程：
- 首先，我们随机选择$ q $中的一个数字，使其成为多项式中第一项的系数$ a^1 \in \mathbb{Z}_q $。
- 随后，我们用同样的方法，依次随机的生成$ a^2, \dots, a^{n-2} $，即一直到第$ n-2 $项的系数。
- 现在最后只剩下最后的一项系数$ a^{n-1} $没有生成了，即第$ n-1 $项。这个时候我们发现，因为前面$ n-2 $项已经确定了，那么如果我们希望这个多项式是$ (x-1) $的倍数，那么它一定要满足：
$$ a^{n-1} + \sum_{i=1}^{n-2} a^i = 0 \text{ mod } \mathbb{Z}q\ a^{n-1} = -\sum{i=1}^{n-2} a^i $$
- 因为我们所有的系数都在$ \mathbb{Z}q $中，所以我们随机生成$ a^{n-1} $的话就是在$ q $个元素中随机的选择一个元素。那么这样随机的选中$ -\sum{i=1}^{n-2} a^i $的可能性就是$ 1/q $了。
这也就是说，任意的给定一个如上描述的Ring-SIS问题，我们如果盲猜$ \tilde{e} $作为解的话，竟然会有$ 1/q $的几率会猜对！
$ 1/q $这个概率对于Ring-SIS的安全性来说实在是太大了。这也就是说，如果我们想要达到SIS问题中我们得到的$ 2^{\widetilde{O}(n)} $的安全性（复杂度）的话，我们需要把$ q $的大小设置为$ q = 2^{\widetilde{O}(n)} $才行。在如此大的q的情况下，就算我们计算Ring-SIS的哈希函数可以通过FFT来加快速度，最后得到的时间复杂度$ O(n \log{nq}) = O(n \log{n \cdot 2^n}) $甚至大于了原本的SIS的时间复杂度。
$ \mathbb{Z}[X]/(X^n+1) $结构的多项式环
因为之前我们用的环的特征多项式可以被约分，所以导致用原本的环构造出的Ring-SIS问题非常好破解。在之前的文章里也提到了解决方案：使用一个特征多项式不能被约分的环来代替。
这个新的多项式环，就是$ \mathbb{Z}[X]/(X^n + 1) $。在这个环下的运算和之前大致相同，唯一不同的是临近$ n $阶时的乘法规则： $$ x \cdot x^i = \begin{cases} x^{i+1} & i < n-1\ -1 & i = n-1 \end{cases} $$ 同理，代表了这个环的循环矩阵中的$ X $为： $$ X = \begin{bmatrix} 0&0&0&-1\ 1&0&0&0\ 0&1&0&0\ 0&0&1&0 \end{bmatrix} $$ 这个新的环的安全性在于特征多项式$ (X^n + 1) $的特殊属性。当$ n $是2的幂的时候，这个多项式又被称作Cyclotomic Polynomial（分圆多项式），而这个多项式是无法被约分的。所以在这个多项式环中，我们上面描述的破解Ring-SIS的方法就无效了。
Ideal Lattice（理想格）
接下来说一说Ideal Lattice的概念。
在环论中，有一类比较特殊的集合叫做理想（Ideal）。假如我们在一个环$ R $中，那么一个理想$ \mathcal{I} \subseteq R $就是环$ R $的一部分。这个理想$ \mathcal{I} $有几个特性：
- 首先，$ \mathcal{I} $这个集合在加法空间内是封闭的（closed under addition），即任意两个理想中的元素$ a, b \in \mathcal{I} $相加或者相减之后也会得到一个理想元素：$ a + b, a-b \in \mathcal{I} $。
- 其次，理想中的元素与环$ R $中的元素在乘法空间内是封闭的（closed under multiplication），即一个环中的元素$ r \in R $和一个理想中的元素$ y \in \mathcal{I} $相乘，最后还会得到理想中的元素：$ ry \in \mathcal{I} $。
在我们的应用场景中，$ R $是一个$ n-1 $阶多项式组成的多项式环。这也就是说，我们可以很简单的把一个$ R $中的元素映射到$ \mathbb{Z}^n $中——只需要把每一个系数作为一个维度就好了。举个例子： $$ 1 + 2x^2 - 3x^3 \rightarrow (1, 2, -3) $$ 解决了$ R $之后，我们来看$ \mathcal{I} $。这里我们要用$ \mathcal{I} $来表示之前描述的$ \mathbb{Z}[x]/(x^n+1) $这么一个特殊的多项式环。我们可以把$ \mathcal{I} $看做一个特殊的Lattice $ \mathcal{I} \subseteq \mathbb{Z}^n $，并且在之前描述过的循环矩阵的变换矩阵$ X $的运算下是封闭的。换句话来说，如果$ y \in \mathcal{I} $，那么$ Xy \in \mathcal{I} $。展开来看的话就是： $$ (y_1, \dots, y_n)^T \in \mathcal{I} \iff (-y_n, y_1, \dots, y_{n-1}) \in \mathcal{I} $$ 我们一般称这样的构造为Anti-cyclic Lattice。反之，如果我们用的是前面$ (X^n -1) $特征多项式对应的线性变换的话，那么得到的Lattice叫做Cyclic Lattice。这就是所谓的理想格了。
理想格其实是一种很奇怪的格结构。假如我们从理想格中选出任意一个非0的向量$ y \in \mathcal{I} $，我们可以依次对这个向量施加线性变换$ X $，并且获得$ n $个线性独立的向量： $$ y, Xy, X^2y, \dots, X^{n-1}y \in \mathbb{Z}^n $$ 我们观察发现，$ X $的Determinant是1，代表$ X $这个线性变换是可以维持原本向量的长度的，这也就是说，这些线性独立的向量的长度全部相等： $$ \lvert\lvert X^iy \rvert\rvert = \lvert\lvert X^jy \rvert\rvert $$ 这代表什么呢？这代表理想格中的最短向量问题SVP与最短独立向量问题SIVP是一样的！这是因为只要存在一个最短的向量$ y’ \in \mathcal{I} $，那么我们就可以通过叠加线性变换$ X $获得其他的$ n-1 $个独立的等长向量，这也就代表了$ \lambda_1(\mathcal{I}) = \lambda_n(\mathcal{I}) $。这样一来，在理想格中，有一部分原本的格的假设变得不同了，原本在普通的格中我们认为困难的问题，在理想格中可能很容易解决，或者难以证明难度。
理想格难题与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并不是纯粹的一个理想格问题，因为它的解是$ (e_1, \dots, e_l) \in R^l $这么一个多项式构成的向量，而并不只是一个理想格元素。
所以现在格密码圈对于Ring-SIS的看法褒贬不一。一部分的人认为Ring-SIS可以很有效的提高格密码的运算效率，所以提倡它的普及应用。但是另一部分人认为Ring-SIS的难度规约还没有完成，所以不像SIS、LWE一样，我们不能完全的相信它的安全性。
不过密码学就是这样，有很多情怀的因素在里面。目前主流的同态加密库如HELib、TFHE等等都是使用多项式环来进行优化计算。
Credits
The contents of this post is summarized from Prof. Vinod Vaikuntanathan’s CS294 course.