NTRU：历史、设计与安全性

NTRU 由 Hoffstein、Pipher 和 Silverman 于 1996 年发明，是目前仍被认为安全的最古老后量子公钥系统之一。不同于依赖数论困难性的 RSA 和 ECC，NTRU 的安全性基于这样一个困难问题：在由多项式环导出的特定晶格中寻找短向量。后量子密码学成为主流之前，NTRU 已实现商业化并部署于多种安全产品中。

NTRU 在截断多项式环 Z[X]/(X^N - 1) 中运行，其中 N 是素数。该环中的多项式次数最多为 N-1，乘法会回绕（卷积）。环的选择以及小系数多项式的结构，是 NTRU 效率和安全性的重要基础。

密钥生成会选择两个小多项式 f 和 g，其系数属于 {-1, 0, 1}。多项式 f 必须同时在 p（较小的素数，通常为 3）和 q（较大的素数，通常为 2048）模下可逆。公钥为 h = f_q^{-1} * g mod q，其中 f_q 是 f 模 q 的逆元。私钥是二元组 (f, g)。

要加密一个系数较小的消息多项式 m，发送方选择一个随机的小型盲化多项式 r，并计算 c = r * h + m mod q。密文 c 是同一环中的多项式。随机值 r 可防止同一消息的两次加密呈现出相同结果，从而实现语义安全性。

解密时计算 a = f * c mod q，并将系数选取在区间 (-q/2, q/2] 内。然后，a mod p 可恢复 f_p * m mod p，再乘以 fp = f^{-1} mod p 即可得到 m。小误差结构确保 f * c 的系数足够小，使 mod q 和 mod p 运算能够正确配合，在没有噪声导致解密失败的情况下恢复消息。

现代 NTRU 有两个标准化参数系列：NTRU-HPS（Hoffstein-Pipher-Silverman）和 NTRU-HRSS（Hulsing-Rijneveld-Schanck-Schwabe）。NTRU-HPS 使用三元消息多项式，而 NTRU-HRSS 使用随机化编码，以获得更低的解密失败率。两者都入围了 NIST PQC 第三轮，参数集分别面向 128 位、192 位和 256 位安全性。

目前尚无针对参数设置恰当的 NTRU 的多项式时间攻击。最有效的攻击可归结为在 NTRU 晶格中寻找短向量，这是近似 SVP 问题的一个实例。NTRU 晶格具有特定结构（循环矩阵块），因此比随机晶格稍微容易攻击；参数选择会考虑这一结构，并据此留出安全裕量。

NTRU 曾受到 NTRU Cryptosystems Inc.（后来为 Security Innovation）的大量专利保护。最初的专利于 1996 年和 1998 年提交。这种专利保护阻碍了 NTRU 在随后二十年中的广泛采用和开源实现。NTRU 的核心专利于 2017 年前后到期，此后开源实现大量出现，NTRU 也参加了 NIST PQC 标准化竞赛。

NTRU 与 Kyber、Classic McEliece 和 SABER 一同入围了 NIST PQC 第三轮。NIST 最终选择 Kyber（ML-KEM）作为主要的 KEM 标准，理由是其安全性分析更简单、设计更简洁。NTRU 虽未被标准化，但仍是可行的替代方案，其安全性分析也促进了人们对晶格安全性的理解。

NTRUPrime 由 Bernstein、Chuengsatiansup、Lange 和 van Vredendaal 开发，有意移除环结构 X^N - 1，改用 X^N - X - 1，即一个次数为素数的多项式。这消除了循环环结构可能带来的潜在弱点；一些密码分析人员认为这些弱点可能被利用。NTRUPrime 也曾是 NIST PQC 的备选候选方案。

NTRU 早于基于 LWE 的方案，并不像 Regev 的 LWE 归约那样具有形式化的最坏情况困难性归约。不过，在相同安全级别下，与许多 LWE 方案相比，NTRU 的密钥生成速度更快、密文大小更小。代价是其安全性基础不够形式化，更多依赖数十年的密码分析经验，而不是归约证明。

在 NTRU 中，公钥由什么导出？

NTRU 是一种基于多项式环运算的先驱性晶格密码系统。密钥生成使用小多项式 f 和 g，公钥为 h = f^{-1}*g mod q。加密使用随机盲化；解密则利用 f 的小系数结构。NTRU 没有形式化的最坏情况归约，但经受住了数十年的密码分析考验。其专利于 2017 年到期，并入围了 NIST PQC 第三轮。