NTRU 格密码系统：从多项式环到 NIST 落选者的安全分析

算法原理 · 2026-07-23

概述

在格基密码学（Lattice-Based Cryptography）的发展史上，有两个里程碑式的方案几乎同时出现在 20 世纪 90 年代，却走向了截然不同的命运。一个是 1996 年由 Jeffrey Hoffstein、Jill Pipher 和 Joseph Silverman 提出的 NTRU（Next Thrill of the Realm of encryption，最初拟作 "Number Theorists Rejoice"）公钥密码系统；另一个是 2001 年Ajtai 的最坏情况归约理论以及 2005 年 Regev 形式化的 Learning With Errors (LWE) 问题。

NTRU 的独特之处在于：它先有方案，后有理论。1996 年论文发表时，NTRU 的安全性仅基于启发式的格困难问题假设——设计者观察到破解 NTRU 似乎需要求解格中的最短向量问题（Shortest Vector Problem, SVP），但未能给出严格的形式化归约。直到多年后，NTRU 才被纳入 Gentry-Peikert-Vaikuntanathan（GPV）框架，获得了部分理论支撑。相比之下，LWE 从诞生之日起就带有 Regev 证明的"最坏情况到平均情况归约"——这是一个"先有理论、后有方案"的优雅范式。

这种"理论成熟度"的差异，在 2022 年 NIST 后量子密码标准化竞赛的最终选择中产生了决定性影响。CRYSTALS-Kyber（基于 Module-LWE）被选为唯一的 KEM 标准，而 NTRU 家族虽进入第三轮最终候选，却最终落选。 这不是因为 NTRU 被攻破——它经受住了近三十年的公开密码分析——而是因为 NIST 在同等安全性下更青睐理论论证"更干净"的方案。

理解 NTRU，就是理解格基密码学从"工程直觉"走向"形式化安全"的完整叙事。

TEXT

┌─────────────────────────────────────────────────────────────────┐
│                    格基密码学的两条路线                           │
├────────────────────────────┬────────────────────────────────────┤
│  NTRU 路线                  │  LWE 路线                          │
│  (1996, Hoffstein et al.)  │  (2005, Regev)                    │
├────────────────────────────┼────────────────────────────────────┤
│  先有方案，后有理论           │  先有理论，后有方案                  │
│  多项式环 Z[x]/(x^N-1)     │  矩阵 A, b = As + e                │
│  卷积乘法，NTT 加速          │  矩阵-向量乘法                     │
│  启发式安全 → GPV 框架      │  最坏情况归约（GapSVP → LWE）       │
│  三十年密码分析史            │  二十年密码分析史                   │
│  NIST PQC 第三轮            │  NIST PQC 标准（FIPS 203/204）      │
└────────────────────────────┴────────────────────────────────────┘

数学基础：截断多项积环

NTRU 的所有运算都在一个特殊的代数结构上进行——截断多项式环（Truncated Polynomial Ring）。

环的定义

设 $N$ 为一个正整数（通常取素数），NTRU 的工作环为：

$$R = \mathbb{Z}[x] / (x^N - 1)$$

这个环中的元素是次数小于 $N$ 的整系数多项式：

$$f(x) = f_0 + f_1 x + f_2 x^2 + \cdots + f_{N-1} x^{N-1}, \quad f_i \in \mathbb{Z}$$

环中的乘法是卷积积（convolution product），即在模 $x^N - 1$ 下的多项式乘法：

$$(f \cdot g)_k = \sum_{i+j \equiv k \pmod{N}} f_i g_j$$

为什么选择这个环？ 原因有二：

代数封闭性：两个次数 $< N$ 的多项式在模 $x^N - 1$ 下相乘，结果仍是次数 $< N$ 的多项式，次数不会"溢出"。
快速计算：卷积积可以通过数论变换（Number Theoretic Transform, NTT）在 $O(N \log N)$ 时间内完成，远优于直接计算的 $O(N^2)$。

三元系数多项式

NTRU 的密钥和噪声多项式通常从三元多项式集合中选取——系数取自 $\{-1, 0, 1\}$。具体来说：

$T(d_1, d_2)$：恰好有 $d_1$ 个系数为 $+1$、$d_2$ 个系数为 $-1$、其余为 $0$ 的多项式集合
例如 $T(128, 128)$ 表示一个有 $N = 701$ 次、256 个非零系数（一半 +1，一半 -1）的多项式

三元多项式的稀疏性（非零系数少）是 NTRU 安全性的关键——稀疏多项式乘积的系数分布具有特殊结构，攻击者可以利用这种结构进行格攻击。

NTRU 格结构

NTRU 的安全性可以归约为一个特定格上的困难问题。给定公钥 $h$，定义 $2N$ 维格：

$$\mathcal{L}_h = \{ (u, v) \in R^2 : u \cdot h \equiv v \pmod{q} \}$$

这个格的基由以下矩阵给出：

$$\begin{pmatrix} I_N & h \\ 0 & q I_N \end{pmatrix}$$

其中 $I_N$ 是 $N \times N$ 单位矩阵。NTRU 的私钥 $(f, g)$ 对应这个格中的短向量——因为 $f$ 和 $g$ 的系数都很小（三元），所以 $(f, g)$ 的欧几里得范数远小于随机格向量的期望范数。

安全假设：在 $\mathcal{L}_h$ 中找到最短向量等价于破解 NTRU。这个格被称为 NTRU 格，具有特殊的代数结构（循环块结构），使得格规约算法可以在略低于一般格的复杂度下求解——这就是为什么 NTRU 的参数选择需要比无结构格更大的维度。

算法描述

NTRU 的三个核心算法如下：

密钥生成

输入：参数 $(N, p, q, d)$，其中：

$N$：多项式次数（素数）
$p$：小模数（通常为 3），用于消息编码
$q$：大模数（通常为 2 的幂，如 $q = 2048$），需 $\gcd(p, q) = 1$
$d$：控制多项式稀疏性的参数

流程：

随机选择 $f \in T(d+1, d)$，确保 $f$ 在模 $p$ 和模 $q$ 下都可逆
计算 $f_p^{-1} \bmod p$ 和 $f_q^{-1} \bmod q$
随机选择 $g \in T(d, d)$
计算公钥：$h = p \cdot f_q^{-1} \cdot g \pmod{q}$
私钥：$(f, f_p^{-1})$

公钥尺寸：$N \log_2 q$ 比特。当 $N = 701, q = 2048$ 时，公钥约 877 字节。

加密

输入：明文 $m \in R$（系数在 $\{-1, 0, 1\}$ 中，编码后映射到 $\mathbb{Z}_p$），公钥 $h$

流程：

选择随机"盲化"多项式 $r \in T(d, d)$
计算密文：$e = r \cdot h + m \pmod{q}$

密文尺寸：与公钥相同，$N \log_2 q$ 比特。

解密

输入：密文 $e$，私钥 $f$

流程：

计算 $a = f \cdot e \pmod{q}$，将系数调整到 $[-q/2, q/2]$
计算 $b = a \bmod p$
计算明文 $m = f_p^{-1} \cdot b \pmod{p}$

正确性验证：

$$a = f \cdot (r \cdot h + m) = f \cdot r \cdot h + f \cdot m \pmod{q}$$

代入 $h = p \cdot f_q^{-1} \cdot g$：

$$a = p \cdot r \cdot g + f \cdot m \pmod{q}$$

因为 $r, g, f, m$ 的系数都很小（三元），所以 $p \cdot r \cdot g + f \cdot m$ 的系数在模 $q$ 下不会发生回绕（wrap around），于是：

$$a = p \cdot r \cdot g + f \cdot m \quad \text{（在整数上成立）}$$

再模 $p$ 得到 $b = f \cdot m \bmod p$，乘以 $f_p^{-1}$ 即恢复 $m$。

安全性分析

已知攻击方法

NTRU 的安全性分析是密码学中最活跃的领域之一，近三十年间涌现了多种攻击路线：

#### 1. 格规约攻击（Lattice Reduction Attack）

这是最直接的攻击方法：将 NTRU 公钥 $h$ 嵌入 NTRU 格 $\mathcal{L}_h$，使用 LLL 或 BKZ 算法寻找短向量 $(f, g)$。

BKZ（Block Korkine-Zolotarev）算法的块大小 $\beta$ 与攻击成功率密切相关：

$\beta = 20$：可破解早期 NTRU 小参数
$\beta \geq 200$：需要现代推荐参数（$N \geq 701$）
$\beta \to \infty$：理论上可破解任意 NTRU，但时间复杂度指数增长

安全参数选择原则：$N$ 需要足够大，使得 BKZ-$\beta$ 在 $\beta \approx N/2$ 时才能成功——这意味着攻击复杂度约为 $2^{N/2}$ 量级。

#### 2. 选择密文攻击（Chosen Ciphertext Attack）

如果攻击者可以提交任意密文并获取解密结果（或解密是否成功的反馈），可以利用 NTRU 的代数结构恢复私钥。防护方法：使用 Fujisaki-Okamoto 变换（或其他 CCA 安全转换）将 CPA-安全的 NTRU 提升为 CCA-安全的 KEM。

#### 3. 侧信道攻击（Side-Channel Attack）

NTRU 的多项式乘法实现如果不注意恒定时间（constant-time）特性，可能泄露私钥信息：

计时攻击：NTT 的执行时间可能依赖输入系数的值
功耗分析：稀疏多项式的乘法功耗模式与密集多项式不同
故障注入：在 NTT 计算中注入故障可导致私钥泄露

防护措施：恒定时间实现、掩码技术（masking）、冗余计算。

与 LWE 变体的安全性对比

维度	NTRU	ML-KEM（Module-LWE）
底层困难问题	NTRU 格上的近似 SVP	Module-LWE
最坏情况归约	部分（GPV 框架，归约有损失）	直接（LWE → GapSVP，归约紧致）
代数结构	循环块结构（可利用）	模结构（结构更弱）
密码分析历史	30 年	20 年
推荐参数尺寸	公钥 ~1 KB	公钥 ~1.2 KB

关键洞察：NTRU 的循环块结构是一把双刃剑。一方面，它使 NTRU 的计算速度极快（NTT 加速的卷积乘法）；另一方面，这种结构可能为攻击者提供额外的"捷径"——格规约算法在处理循环格时，可以利用对称性降低约简成本。因此 NTRU 需要选择比无结构 MLWE 更大的参数来达到同等安全级别。

NIST PQC 竞赛历程

竞赛表现

NTRU 家族在 NIST 后量子密码标准化竞赛中以两种变体参赛：

NTRU-HPS（Hoffstein-Pipher-Silverman 原始设计）：使用三元多项式
NTRU-HRSS（Hülsing-Rijneveld-Schanck）：改进版本，优化参数选择

两种变体均通过了第一轮（2017-2019）和第二轮（2019-2020）评估，进入第三轮最终候选名单（2020-2022）。

落选原因深度分析

2022 年 7 月，NIST 选择 CRYSTALS-Kyber（基于 Module-LWE）作为唯一的 KEM 标准，NTRU 与 SABER 一同落选。核心原因不是安全性或性能，而是理论论证的质量：

归约质量（Reduction Quality）

- Kyber 基于 MLWE，拥有从最坏情况 GapSVP 的直接归约（Regev 2005, Peikert 2009, Langlois-Stehlé 2015） - NTRU 到最坏情况格问题的归约需要经过 GPV 框架，且归约过程中存在安全损失（security loss）——为了达到相同的安全级别，NTRU 需要更大的参数

实现一致性（Implementation Uniformity）

- Kyber 的三个安全级别（512/768/1024）仅通过改变模格维度实现，代码路径高度统一 - NTRU 的不同参数集涉及不同的多项式度数（如 $N = 659, 701, 821$）和模数选择，各级别的代码实现差异更大

解封装失败率（Decapsulation Failure Rate）

- Kyber 经 FO 变换后解封装失败概率严格为零（通过参数选择保证） - NTRU-HPS 存在微小但非零的解封装失败率（约 $2^{-128}$ 量级），需要额外的错误处理逻辑

密码分析密度

- 截至 2022 年，针对 LWE/MLWE 的密码分析论文数量远多于 NTRU，说明 LWE 经受了更密集的学术检验

NTRU 的"遗产"

虽然 NTRU 落选为 KEM 标准，但它的影响力远未结束：

FALCON（基于 NTRU 格上的 GPV 框架）被选为数字签名标准（FIPS 206），NTRU 格的代数结构使其能够生成极为紧凑的签名
NTRU Prime（由 Bernstein 等人提出）作为 NTRU 的"净化"版本，消除了原始 NTRU 中可能存在安全风险的代数结构，继续参与 NIST 额外签名征集
NTRU 的高效多项式乘法技术被所有格基方案采用——Kyber、Dilithium、FALCON 都使用 NTT 加速的卷积乘法，这正是 NTRU 的核心贡献

国密视角下的 NTRU

与国密算法的关系

NTRU 作为国际格基密码的代表，与国密 SM2/SM3/SM4 体系存在有趣的对照：

维度	国密体系	NTRU / LWE 体系
算法基础	椭圆曲线密码（SM2）+ 分组密码（SM4）	格密码
安全假设	椭圆曲线离散对数（ECDLP）	格上近似 SVP / LWE
量子威胁	Shor 算法可破解 ECDLP	目前无有效量子算法
标准推进	国家密码管理局	NIST（美国）
部署状态	国内金融、政务大规模部署	国际互联网（TLS 1.3 混合模式）

NTRU 对国密改造的启示

对于正在进行国密改造的企业，NTRU 的故事提供了三个重要启示：

最坏情况归约的重要性：国密改造方案在未来量子威胁下的长期安全性，需要类似 LWE 的严格归约支撑，而非仅依赖启发式安全
算法多样性（Crypto-Agility）：不应将全部安全押注在单一数学假设上——即使格密码整体安全，不同变体（NTRU vs Module-LWE）的安全裕度也不同
混合模式过渡：在国密与国际后量子算法之间建立混合模式，可以平滑迁移风险

总结

NTRU 是密码学中一个罕见的案例——一个先于理论三十年诞生的方案，凭借工程直觉和持续的分析改进，经受住了近三十年的公开密码分析，最终在标准化竞争中败给了理论更年轻的对手。它的故事揭示了密码学标准化的核心逻辑：在安全性相当的方案之间，理论论证的"干净程度"往往比性能的微小优势更具决定性意义。

对于读者而言，理解 NTRU 不仅是学习一个具体的密码系统，更是理解格基密码学从直觉驱动走向理论驱动的完整叙事。NTRU 的落选并不意味着它的失败——FALCON 的标准化、NTT 技术的广泛采用、以及 NTRU Prime 的持续演进，都证明了 NTRU 家族在密码学生态中的持久生命力。