Ring-LWE 密码学：从格问题到后量子标准的代数优化

密码学概念 · 2026-09-14

概述

Ring-LWE（Ring Learning With Errors）是 Learning With Errors 问题的代数结构化变体，由 Lyubashevsky、Peikert 和 Regev 于 2010 年提出。它将标准 LWE 中的向量空间 $\mathbb{Z}_q^n$ 替换为多项式环 $R_q = \mathbb{Z}_q[x]/\langle x^n + 1 \rangle$，利用环的代数结构实现了两个关键优化：

维度	标准 LWE	Ring-LWE	改进幅度
公钥尺寸	$O(n^2 \log q)$ 比特	$O(n \log q)$ 比特	降低约 $n/2$ 倍
乘法复杂度	$O(n^2)$	$O(n \log n)$	NTT 加速
安全性归约	最坏情况到平均情况	理想格上的 SIVP	结构更紧

Ring-LWE 的核心价值在于：利用环结构在不损失安全性的前提下大幅降低计算开销，使其成为 NIST 后量子密码标准化中 ML-KEM（FIPS 203）和 ML-DSA（FIPS 204）的直接数学基础。

数学结构：多项式环 $R_q$

环的定义

设 $n$ 为 2 的幂（称为次数），$q$ 为满足 $q \equiv 1 \pmod{2n}$ 的素数。定义多项式环：

$$R_q = \mathbb{Z}_q[x] / \langle x^n + 1 \rangle$$

环中元素是次数小于 $n$、系数在 $\mathbb{Z}_q$ 中的多项式：

$$a(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1}$$

加法逐系数进行，乘法在模 $x^n + 1$ 下进行——即 $x^n = -1$，$x^{n+1} = -x$，依此类推。

分圆域与离散傅里叶变换

多项式 $x^n + 1$ 是 $2n$ 次本原单位根 $\zeta_{2n} = e^{\pi i / n}$ 在有理数域上的极小多项式。定义 $n$ 个根：

$$\zeta_{2n}^{2j-1}, \quad j = 1, 2, \ldots, n$$

这些根在 $\mathbb{Z}_q$ 中存在对应的整数表示。当 $q \equiv 1 \pmod{2n}$ 时，存在整数 $\omega$ 使得 $\omega^{2n} \equiv 1 \pmod{q}$，且 $\omega^n \equiv -1 \pmod{q}$。此时 $x^n + 1$ 在 $\mathbb{Z}_q$ 中完全分裂：

$$x^n + 1 \equiv \prod_{j=1}^{n} (x - \omega^{2j-1}) \pmod{q}$$

中国剩余定理表示

利用中国剩余定理，环 $R_q$ 同构于 $n$ 个 $\mathbb{Z}_q$ 的直积：

$$R_q \cong \mathbb{Z}_q^n$$

具体地，多项式 $a(x)$ 可映射为其在 $n$ 个根处的取值向量：

$$\text{Eval}(a) = (a(\omega^1), a(\omega^3), \ldots, a(\omega^{2n-1})) \in \mathbb{Z}_q^n$$

在这个表示下，环乘法变为逐坐标乘法：

$$\text{Eval}(a \cdot b) = \text{Eval}(a) \circ \text{Eval}(b)$$

其中 $\circ$ 表示逐元素乘法。这种同构关系正是数论变换（NTT, Number Theoretic Transform）的基础，使得多项式乘法可以在 $O(n \log n)$ 时间内完成。

Ring-LWE 问题定义

分布采样

给定安全参数 $n$、模数 $q$ 和误差分布 $\chi$（通常为中心离散高斯分布），Ring-LWE 分布 $A_{s,\chi}$ 按如下方式采样：

均匀随机选择 $a(x) \leftarrow R_q$
从 $\chi$ 中采样误差多项式 $e(x) \leftarrow \chi^n$
均匀随机选择秘密多项式 $s(x) \leftarrow R_q$
输出 $(a(x), b(x) = a(x) \cdot s(x) + e(x) \pmod{x^n + 1, q})$

搜索版本与判定版本

搜索版本 Ring-LWE（Search-Ring-LWE）：给定 $m$ 个样本 $(a_i, b_i)$，恢复秘密 $s(x)$。

判定版本 Ring-LWE（Decision-Ring-LWE）：区分以下两个分布：

$\mathcal{D}_0 = \{(a_i, b_i)\}$ 来自 Ring-LWE 分布
$\mathcal{D}_1 = \{(a_i, u_i)\}$ 其中 $u_i$ 均匀随机分布在 $R_q$

困难性假设：对于适当的参数选择，Search-Ring-LWE 和 Decision-Ring-LWE 都是计算困难的。

安全性分析

最坏情况到平均情况的归约

Lyubashevsky、Peikert 和 Regev 证明了以下关键定理：

定理（LPR10）：如果存在多项式时间算法解决 Decision-Ring-LWE，则存在多项式时间（经典）算法解决理想格（ideal lattice）上的近似最短向量问题 $\tilde{O}(\sqrt{n})$-SIVP。

理想格是满足特殊对称性的格：理想格 $I \subseteq R$ 是环 $R$ 的子模，对环乘法封闭。这一归约比标准 LWE 的归约更紧，因为利用了环结构的额外信息。

与标准 LWE 的安全性对比

性质	标准 LWE	Ring-LWE
困难性问题	SIVP（一般格）	SIVP（理想格）
归约强度	最坏情况到平均情况	最坏情况到平均情况
量子抗性	✅	✅
参数选择灵活性	高	受环结构限制

关键洞察：理想格是一般格的子类，因此 Ring-LWE 的安全性假设略弱于标准 LWE。但由于目前没有针对理想格的专用高效攻击算法，Ring-LWE 在实际中被认为足够安全。

已知攻击与参数选择

#### 格归约攻击

Ring-LWE 的安全性依赖于格基归约算法（如 LLL、BKZ）的难度。当前最佳攻击参数估算使用 LWE Estimator（https://github.com/latte-hack/lwe_estimator）。

对于 $n = 512$、$q = 7681$ 的典型参数：

BKZ-256 攻击需要约 $2^{128}$ 次操作
对应 NIST Level 1 安全强度

#### 代数攻击风险

Ring-LWE 的特殊结构可能引入额外攻击面：

子群攻击：利用环的理想子结构
对偶攻击：针对理想格的对偶格攻击
侧信道攻击：NTT 实现的常量时间问题

防护建议：实际部署时应采用常量时间 NTT 实现，并进行侧信道防护。

密码学构造

Ring-LWE 公钥加密

基于 Ring-LWE 的公钥加密方案（如 Kyber/KEM）包含以下算法：

#### 密钥生成

采样 $A \leftarrow R_q^{k \times k}$（矩阵）
采样秘密 $s \leftarrow R_q^k$（误差分布）
采样错误 $e \leftarrow R_q^k$
计算 $t = A \cdot s + e$
公钥 $(pk) = (A, t)$，私钥 $(sk) = s$

#### 加密

给定消息 $m \in \{0,1\}^\lambda$：

采样随机多项式 $r \leftarrow R_q$
采样错误 $e_1, e_2 \leftarrow \chi$
计算 $u = A^T \cdot r + e_1$
计算 $v = t^T \cdot r + e_2 + \lfloor q/2 \rfloor \cdot m$
密文 $c = (u, v)$

#### 解密

给定密文 $(u, v)$ 和私钥 $s$：

计算 $m' = v - s^T \cdot u$
对每个系数取最近的整数并映射回 $\{0,1\}$

正确性保证：误差项 $e_2 - s^T \cdot e_1$ 必须足够小，使得解密时不会跨越阈值。

Ring-LWE 数字签名

Ring-LWE 签名方案（如 Dilithium/ML-DSA）基于拒绝采样技术：

#### 密钥生成

采样 $A \leftarrow R_q^{l \times k}$
采样秘密 $s_1, s_2$（误差分布）
计算 $t = A \cdot s_1 + s_2$
公钥 $(pk) = (A, t)$，私钥 $(sk) = s_1, s_2$

#### 签名

给定消息 $m$：

采样临时密钥 $y$
计算 $w = A \cdot y$
挑战 $c = H(m, w)$（哈希函数）
计算响应 $z = c \cdot s_1 + y$
拒绝采样：检查 $z$ 的范数是否足够小
签名 $\sigma = (z, c)$

#### 验证

给定 $(m, \sigma = (z, c))$：

计算 $w' = A \cdot z - t \cdot c$
重新计算挑战 $c' = H(m, w')$
验证 $c = c'$ 且 $z$ 的范数足够小

基于 Ring-LWE 的身份基加密

Ring-LWE 也可用于构造身份基加密（IBE）方案：

系统参数：$(n, q, \chi)$ 和安全参数 $\lambda$
主密钥生成：采样主秘密 $master\_sk$
主公钥：$master\_pk = H(master\_sk)$（哈希到环）
用户密钥派生：基于身份 $ID$ 派生私钥
加密：使用身份作为公钥

工程实现：NTT 加速

为什么需要 NTT

Ring-LWE 的核心操作是多项式乘法。朴素乘法复杂度为 $O(n^2)$，而 NTT 可将其降至 $O(n \log n)$。

NTT 原理：利用分圆域的离散傅里叶变换性质，将多项式乘法转化为：

$$\text{Multiplication}(a, b) = \text{INTT}(\text{NTT}(a) \circ \text{NTT}(b))$$

具体实现

以 Kyber-768 为例（$n = 256, q = 3329$）：

PYTHON

# 简化的 NTT 实现示意（非生产代码）
def ntt(a):
    """数论变换"""
    # 位反转置换
    a = bit_reverse_permute(a)
    # 迭代计算
    length = 2
    while length <= n:
        root = pow(g, (q - 1) // length, q)  # 原根
        for i in range(0, n, length):
            w = 1
            for j in range(i, i + length // 2):
                u = a[j]
                v = a[j + length // 2] * w % q
                a[j] = (u + v) % q
                a[j + length // 2] = (u - v) % q
                w = w * root % q
        length *= 2
    return a

参数选择实践

NIST PQC 标准化的参数选择遵循以下原则：

安全级别	$n$	$q$	$k$ (Kyber)	对应 NIST 级别
Level 1	256	3329	2	128-bit
Level 3	256	3329	3	192-bit
Level 5	512	12289	4	256-bit

参数选择的权衡：

更大的 $n$：更强的安全性，但更高的计算开销
更大的 $q$：更多的安全边际，但密文尺寸增加
更大的 $k$：更强的安全性，但密钥和密文尺寸线性增长

Ring-LWE vs 其他格密码方案

与标准 LWE 的对比

维度	标准 LWE	Ring-LWE	Module-LWE
数学结构	向量空间 $\mathbb{Z}_q^n$	多项式环 $R_q$	自由模 $R_q^k$
密钥尺寸	$O(n^2)$	$O(n)$	$O(kn)$
计算复杂度	$O(n^2)$	$O(n \log n)$	$O(kn \log n)$
安全性	最强（一般格）	中等（理想格）	较强（模块格）
实际应用	理论参考	Kyber、Dilithium	Kyber、Dilithium

Module-LWE 折中：NIST 标准化最终采用 Module-LWE（模 LWE），它是 Ring-LWE 的推广：

$$R_q^k = (R_q)^k = R_q \times R_q \times \cdots \times R_q$$

Module-LWE 保留了 Ring-LWE 的计算效率，同时通过模数 $k$ 提供了更大的安全性调节空间。

与 NTRU 的关系

Ring-LWE 与 NTRU 都基于多项式环，但安全假设不同：

特性	NTRU	Ring-LWE
困难问题	SVP（最短向量问题）	LWE（带学习误差）
安全性证明	弱（基于特殊格结构）	强（worst-case to average-case）
密文尺寸	较小	中等
标准化状态	落选 NIST PQC	入选 ML-KEM/ML-DSA

Ring-LWE 可以被视为 NTRU 的"带误差版本"——NTRU 在环上直接求解短向量问题，而 Ring-LWE 在环上求解带噪声的线性方程问题。

国密视角：Ring-LWE 与国密算法

国密体系中的格密码现状

截至 2026 年，国密算法体系主要基于椭圆曲线（SM2）、分组密码（SM4）和哈希函数（SM3），尚未有基于 Ring-LWE 的国密标准。但这并不意味着 Ring-LWE 与国密无关：

混合密钥交换：SM2 + ML-KEM 混合模式可在过渡期提供双保险
后量子迁移：国密改造系统需考虑长期安全，Ring-LWE 方案可作为后量子替代
隐私计算：基于 Ring-LWE 的全同态加密（BFV/CKKS）与 SM4 结合可实现安全多方计算

国密场景下的选择建议

场景	推荐方案	理由
短期部署（< 5 年）	SM2 + SM4	成熟稳定，密评合规
中期部署（5-10 年）	SM2 + ML-KEM 混合	兼顾当前合规与后量子安全
长期部署（> 10 年）	ML-KEM 或 ML-DSA	抗量子，面向未来

关键建议：在国密改造项目中，应预留后量子迁移接口，以便未来平滑过渡到 Ring-LWE 基础的标准。

实现要点与陷阱

1. 常量时间实现

NTT 实现的常量时间是侧信道防护的关键。非恒定时间的 NTT 可能导致密钥泄露。