本文取材于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\)环中的多项式的过程:

  1. 首先,我们随机选择\(q\)中的一个数字,使其成为多项式中第一项的系数\(a^1 \in \mathbb{Z}_q\)。
  2. 随后,我们用同样的方法,依次随机的生成\(a^2, \dots, a^{n-2}\),即一直到第\(n-2\)项的系数。
  3. 现在最后只剩下最后的一项系数\(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\]
  1. 因为我们所有的系数都在\(\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}\)有几个特性:

  1. 首先,\(\mathcal{I}\)这个集合在加法空间内是封闭的(closed under addition),即任意两个理想中的元素\(a, b \in \mathcal{I}\)相加或者相减之后也会得到一个理想元素:\(a + b, a-b \in \mathcal{I}\)。
  2. 其次,理想中的元素与环\(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.