格密码--Ring-SIS和Ring-LWE

1. 多项式环（Polynomial Rings）

设 $f\in \mathbb{Z}[x]$ 是首一多项式（最高次项系数为1）
则环 $R=\mathbb{Z}[x]/(f)$
元素为：所有次数 $<\mathrm{deg}(f)$ 的多项式。

运算规则：

• 加法：逐系数模整数加法。
• 乘法：计算多项式乘积后模 $f(x)$ 取余（余式次数 $<\mathrm{deg}(f)$）。

多项式的向量表示：
多项式 $a(x)=\sum _{i=0}^{n-1}{a}_i{x}^i$ 对应系数向量 $\mathbf{a}=(a_0,a_1,\dots ,a_{n-1})\in {\mathbb{Z}}^n$。
例如：
$R=\mathbb{Z}[x]/(x^4+2x^2-11x+1)$ 中，
$a(x)=23+11x^2+7x^3\leftrightarrow (23,0,11,7)$.

---

2. 理想格（Ideal Lattices）

理想：
全称：理想子环

定义：$(R，+，.)$是环，$I$是$R$的非空子集。如果$(I,+,.)$满足以下条件：

• 加法子群：$(I,+)$是$(R,+)$的子群
• 乘法吸收律：$\forall r\in R,\forall a\in I\Rightarrow ra\in I(ar\in I)$

则称$I$是$R$的左（右）理想。

理想的判断：
(R,+,.)是环，I是R的左（右）理想，
$\forall a,b\in I,\forall r\in R$当且仅当，$I$满足以下条件：

• 加法子群：$(I,+)$是$(R,+)$的子群（加法封闭性：$a+b\in I$加法逆元：$-a\in I$）
• 乘法吸收律：$ra\in I(ar\in I)$

理想三巨头：

主理想：由单个多项式生成 ⟨a(x)⟩={a(x)r(x)modf∣r∈R}\langle a(x) \rangle = \{ a(x) r(x) \mod f \mid r \in R \}⟨a(x)⟩={a(x)r(x)modf∣r∈R}。 （ 环 $R=\mathbb{Z}[x]/(f)$ ）

理想格：
理想 $I$ 中所有多项式系数向量构成的整数格 $L(I)\subset {\mathbb{R}}^n$。（理想本身就满足群的性质）
本篇仅考虑 $f(x)=x^n-1$（循环格）或 $f(x)=x^n+1$（反循环格）。

---

3. 循环格与反循环格（结构化的格）

(1)循环格

循环格最早在2002年被Micciancio研究
定义：

设 $L\subseteq {\mathbb{Z}}^n$ 是一个格。若对任意向量 $\mathbf{v}=(v_0,v_1,\dots ,v_{n-1})\in L$，其左循环移位 $(v_{n-1},v_0,v_1,\dots ,v_{n-2})\in L$，则 $L$ 称为循环格。
定理：

$R=\mathbb{Z}[x]/(x^n-1)$，则其每一个理想格都是循环格。
ps理想与格关系：每个理想都对应一个格（理想定义天然包含离散子群的条件）

主理想中的多项式通过系数提取转化为向量，这些向量的全体构成一个格。

对 $R=\mathbb{Z}[x]/(x^n-1)$ 的主理想$I$= $⟨a(x)⟩$，I={a(x)⋅r(x)mod(xn−1)∣r(x)∈R}I = \left\{ a(x) \cdot r(x) \bmod (x^n - 1) \mid r(x) \in R \right\}I={a(x)⋅r(x)mod(xn−1)∣r(x)∈R}

则其对应的格 ( $L(I)$ ) 定义为： L(I)={系数向量∣p(x)∈I}={s∈Zn∣s=Ar,r∈Zn}L(I) = \{\text{系数向量} \mid p(x) \in I\} = \{\boldsymbol{s} \in \mathbb{Z}^n \mid \boldsymbol{s} = \boldsymbol{A}\boldsymbol{r},\ \boldsymbol{r} \in \mathbb{Z}^n\} L(I)={系数向量∣p(x)∈I}={s∈Zn∣s=Ar, r∈Zn} 其中 ($\mathbf{A}$) 是循环矩阵。
注：（乘积 $s(x)=a(x)\cdot r(x)\mathrm{mod}(x^n-1)$ 的系数向量 $\mathbf{s}$ 由循环卷积给出： $$s_k=\sum _{\begin{array}{c}i+j\equiv k(\mathrm{mod}n)\end{array}}{a}_i{r}_j$$ 这等价于矩阵乘法 $\mathbf{s}=\mathbf{A}\mathbf{r}$。）

关键理解

设 $a(x)=a_0+a_{1}x+\cdots +a_{n-1}{x}^{n-1}$，其系数向量为 $\mathbf{a}=(a_0,a_1,\dots ,a_{n-1}{)}^{\top }$。

理想 $I$ 是$z-$模的生成元是集合 {a(x),xa(x),x2a(x),…,xn−1a(x)}\{ a(x), x a(x), x^2 a(x), \ldots, x^{n-1} a(x) \}{a(x),xa(x),x2a(x),…,xn−1a(x)}。

因为:

将 $r(x)$ 代入 $I$ 中元素的表达式，得： $$a(x)\cdot r(x)=a(x)\cdot \left(r_0+r_{1}x+\cdots +r_{n-1}{x}^{n-1}\right)=r_0\cdot a(x)+r_1\cdot \left(xa(x)\right)+\cdots +r_{n-1}\cdot \left(x^{n-1}a(x)\right)$$ 这说明：$I$ 中任意元素都是 {a(x),xa(x),…,xn−1a(x)}\{ a(x), x a(x), \ldots, x^{n-1} a(x) \}{a(x),xa(x),…,xn−1a(x)} 的 整数线性组合（系数 $r_i\in \mathbb{Z}$）。

即集合 {a(x),xa(x),x2a(x),…,xn−1a(x)}\{ a(x), xa(x), x^2a(x), \dots, x^{n-1}a(x) \}{a(x),xa(x),x2a(x),…,xn−1a(x)} 的系数向量张成格 $L(I)$，其矩阵形式为循环矩阵.
$$\mathbf{A}=\text{circ}(\mathbf{a})=\left[\begin{array}{cccc}{a}_0& a_{n-1}& \cdots & a_1\\ a_1& a_0& \cdots & a_2\\ ⋮& ⋮& \ddots & ⋮\\ a_{n-1}& a_{n-2}& \cdots & a_0\end{array}\right]$$
A可逆条件：$\gcd (a(x),x^n-1)=1$（在 $\mathbb{Q}$ 上）。
记作：$\mathbf{A}=\text{circ}(\mathbf{a})$

(2) 反循环格

定义：

设 $L\subseteq {\mathbb{Z}}^n$ 是一个格。若对任意向量 $\mathbf{v}=(v_0,v_1,\dots ,v_{n-1})\in L$，其反循环移位 $(-v_{n-1},v_0,v_1,\dots ,v_{n-2})\in L$，则 $L$ 称为反循环格。

定理：

设 $R=\mathbb{Z}[x]/(x^n+1)$，则其每一个理想格都是反循环格。

ps 理想与格关系：每个理想都对应一个格（理想定义天然包含离散子群的条件）。

主理想中的多项式通过系数提取转化为向量，这些向量的全体构成一个格。

主理想对应的格

对 $R=\mathbb{Z}[x]/(x^n+1)$ 的主理想 $I=⟨a(x)⟩$，
I={a(x)⋅r(x)mod(xn+1)∣r(x)∈R}I = \left\{ a(x) \cdot r(x) \bmod (x^n + 1) \mid r(x) \in R \right\}I={a(x)⋅r(x)mod(xn+1)∣r(x)∈R}

则其对应的格 $L(I)$ 定义为：
L(I)={系数向量∣p(x)∈I}={s∈Zn∣s=Br,r∈Zn}L(I) = \{\text{系数向量} \mid p(x) \in I\} = \{\boldsymbol{s} \in \mathbb{Z}^n \mid \boldsymbol{s} = \boldsymbol{B}\boldsymbol{r},\ \boldsymbol{r} \in \mathbb{Z}^n\}L(I)={系数向量∣p(x)∈I}={s∈Zn∣s=Br, r∈Zn}

其中 $\mathbf{B}$ 是反循环矩阵。

注：（乘积 $s(x)=a(x)\cdot r(x)\mathrm{mod}(x^n+1)$ 的系数向量 $\mathbf{s}$ 由反循环卷积给出：
$s_k={\sum }_{\begin{array}{c}i+j\equiv k(\mathrm{mod}n)\\ i+j<n\end{array}}{a}_i{r}_j-{\sum }_{\begin{array}{c}i+j\equiv k+n(\mathrm{mod}n)\\ i+j\ge n\end{array}}{a}_i{r}_j$
这等价于矩阵乘法 $\mathbf{s}=\mathbf{B}\mathbf{r}$。

关键理解

设 $a(x)=a_0+a_{1}x+\cdots +a_{n-1}{x}^{n-1}$，其系数向量为 $\mathbf{a}=(a_0,a_1,\dots ,a_{n-1}{)}^{\top }$。

理想 $I$ 作为 $\mathbb{Z}$-模的生成元是集合 {a(x),xa(x),x2a(x),…,xn−1a(x)}\{ a(x), x a(x), x^2 a(x), \ldots, x^{n-1} a(x) \}{a(x),xa(x),x2a(x),…,xn−1a(x)}。

因为：
将 $r(x)$ 代入 $I$ 中元素的表达式，得：
$a(x)\cdot r(x)=a(x)\cdot \left(r_0+r_{1}x+\cdots +r_{n-1}{x}^{n-1}\right)=r_0\cdot a(x)+r_1\cdot \left(xa(x)\right)+\cdots +r_{n-1}\cdot \left(x^{n-1}a(x)\right)$
这说明：$I$ 中任意元素都是 {a(x),xa(x),…,xn−1a(x)}\{ a(x), x a(x), \ldots, x^{n-1} a(x) \}{a(x),xa(x),…,xn−1a(x)} 的整数线性组合（系数 $r_i\in \mathbb{Z}$）。

即集合 {a(x),xa(x),x2a(x),…,xn−1a(x)}\{ a(x), x a(x), x^2 a(x), \dots, x^{n-1} a(x) \}{a(x),xa(x),x2a(x),…,xn−1a(x)} 的系数向量张成格 $L(I)$，其矩阵形式为反循环矩阵：

$$\mathbf{B}=\overline{\text{circ}}(\mathbf{a})=\left[\begin{array}{ccccc}{a}_0& -a_{n-1}& -a_{n-2}& \cdots & -a_1\\ a_1& a_0& -a_{n-1}& \cdots & -a_2\\ a_2& a_1& a_0& \cdots & -a_3\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ a_{n-1}& a_{n-2}& a_{n-3}& \cdots & a_0\end{array}\right]$$

$\mathbf{B}$ 可逆条件：$\gcd (a(x),x^n+1)=1$（在 $\mathbb{Q}$ 上）。
记作$\mathbf{B}=\overline{\text{circ}}(\mathbf{a})$

密码学意义对比

特性	循环格	反循环格
多项式环	$\mathbb{Z}[x]/(x^n-1)$	$\mathbb{Z}[x]/(x^n+1)$
安全强度	较低（$x^n-1$ 可因式分解）	较高（$x^n+1$ 不可约）
移位操作	$(v_{n-1},v_0,\dots ,v_{n-2})$	$(-v_{n-1},v_0,\dots ,v_{n-2})$
应用场景	早期方案（Micciancio 2002）	后量子密码标准（Kyber, Dilithium）

注：反循环格在现代密码学中更常用，因 $x^n+1$ 在 $n=2^w$ 时不可约，提供更强的安全性保证。

---

4. Ring-SIS

2006年由Micciancio和Rosen提出
Ring-SIS$(n,\ell ,q,B)$安全参数 $n$（通常为2的幂），模数 $q$，目标向量数量 $\ell$，范数界 $B$

定义

给定$a_1,\dots ,a_{\ell }\in R_q={\mathbb{Z}}_q[x]/(x^n+1)$。找到非零 $z_1,\dots ,z_{\ell }\in R_q$，使得(多项式卷积相乘)
$$\sum _{i=1}^{\ell }{a}_i{z}_i=0(\mathrm{mod}q),\Vert z_i{\Vert }_{\infty }\le B.$$
等价向量形式：构造分块反循环矩阵 $m=(\ell \times n)$
$\mathbf{A}=[\overline{\text{circ}}({\mathbf{a}}_1)\mid \cdots \mid \overline{\text{circ}}({\mathbf{a}}_{\ell }){]}_{n\times m}$，求非零短向量 $\mathbf{z}\in [-B,B{]}^m$ 使 $\mathbf{A}\mathbf{z}\equiv 0(\mathrm{mod}q)$。

Lyubashevsky和Micciancio证明，求解平均情况下的环-SIS（$\text{Ring-SIS}$）问题，至少与求解最坏情况下反循环格的 $\gamma$-最短向量问题（${\text{SVP}}_{\gamma }$）一样困难。
应用：

---

5. Ring-LWE

2010年由Lyubashevsky、Peikert和Rosen提出
Ring-LWE$(n,k,q,B)$安全参数：$n$（通常为2的幂，即$n=2^w$），实例数量$k$，模数$q$，误差界$B$（满足$B\ll q/2$）

定义

给定$a_1,\dots ,a_k\in R_q={\mathbb{Z}}_q[x]/(x^n+1)$和$b_1,\dots ,b_k\in R_q$，其中$b_i=a_{i}s+e_i$（$s,e_i$为“短多项式”，即系数均在$[-B,B]$中）。找到秘密多项式$s\in R_q$，使得对所有$i=1,\dots ,k$，均满足：
$b_i\equiv a_{i}s+e_i(\mathrm{mod}q),\Vert s{\Vert }_{\infty }\le B_s,\Vert e_i{\Vert }_{\infty }\le B_e.$

等价向量形式

构造分块反循环矩阵：
$\mathbf{A}={\left[\begin{array}{c}\overline{\text{circ}}({\mathbf{a}}_1)\\ \overline{\text{circ}}({\mathbf{a}}_2)\\ ⋮\\ \overline{\text{circ}}({\mathbf{a}}_k)\end{array}\right]}_{kn\times n}$
其中$\overline{\text{circ}}({\mathbf{a}}_i)$是${\mathbf{a}}_i$的反循环矩阵（$n\times n$）。则问题等价于求解$n$维向量$\mathbf{s}$和$kn$维误差向量$\mathbf{e}\in [-B,B{]}^{kn}$，使得：
$\mathbf{A}\mathbf{s}+\mathbf{e}\equiv \mathbf{b}(\mathrm{mod}q)$
（$\mathbf{b}$是$b_1,\dots ,b_k$的系数向量拼接而成的$kn$维向量）。

安全归约

Lyubashevsky、Peikert和Rosen证明：求解平均情况下的Ring-LWE问题，至少与量子算法求解最坏情况下反循环格的$\gamma$-最短整数向量问题（${\text{SIVP}}_{\gamma }$）一样困难。

目前尚未发现利用矩阵$\mathbf{A}$的结构（反循环性）加速求解的攻击，其安全性与一般LWE相当，但效率更高。
应用：

参考资料：
【理想】理想就是一种子环，它具有乘法吸收律_哔哩哔哩_bilibili

https://www.bilibili.com/video/BV1rm4y1r7dV/?spm_id_from=333.1387.top_right_bar_window_history.content.click

https://cryptography101.ca/lattice-based-cryptography/