💻 computer science

PIP-NTT: Towards a Scalable Memory-Parallelized Accelerator for Iterative NTT in PQC

本文提出了 PIP-NTT，一种用于后量子密码学中迭代数论变换的可扩展且内存并行的硬件加速器，该加速器利用四个较小的存储块和一个无乘法重缩放架构，实现了比现有设计显著更高的面积-时间效率。

原作者： Malik Imran, Ayesha Khalid, Ciara Rafferty, Safiullah Khan, Muhammad Rashid, Maire O'Neill

发布于 2026-07-22

📖 1 分钟阅读☕ 轻松阅读

原作者： Malik Imran, Ayesha Khalid, Ciara Rafferty, Safiullah Khan, Muhammad Rashid, Maire O'Neill

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个世界，保护你银行账户、私人信息甚至国家机密的锁都是由纸做的。几十年来，我们一直依赖于像大数分解这样的数学难题来确保这些锁的安全。但科学家们发现，未来的“量子”计算机——它们运行在量子物理学的奇特规则之上——可以通过一种叫做 Shor 算法的技巧，在几秒钟内将这些纸质锁撕碎。为了阻止这种情况，密码学家正在构建基于“格”（Lattices）的新型、超强力锁，这是一种复杂的、多维的数字网格。这些新锁是“后量子密码学”（PQC）中的英雄。然而，这里有一个难点：这些新锁非常沉重且使用缓慢，因为它们需要大量的数值计算。为了让它们能在你的手机或智能恒温器上实用，我们需要构建特殊的、闪电般快速的硬件引擎，以便高效地执行这些计算，而不至于耗尽电池或占用过多空间。这就是一群研究人员正在解决的挑战，他们想要让这些新的数字锁变得足够快，以适应现实世界。

你即将阅读的论文介绍了一种名为 PIP-NTT 的新型硬件引擎，旨在加速一种特定的、至关重要的数学运算，称为数论变换（NTT）。你可以把 NTT 想象成一条神奇的传送带，它重新排列一堆数字，以便它们可以被瞬间相乘。在基于格的密码学领域（例如 NIST 最近标准化的 ML-KEM 方案）中，这种运算是整个系统的核心脉搏。如果 NTT 变慢了，整个安全系统就会陷入停滞。研究人员发现，现有的用于这项工作的引擎通常卡在一种“乒乓”式存储系统中，数据必须在两个大型存储箱之间来回跳跃，从而造成了减慢速度的交通拥堵。他们还注意到，过程的最后一步使用的是一种沉重且耗能的方法来进行清理。

为了解决这个问题，作者构建了一个更聪明、更精简的引擎。他们没有使用两个巨大的存储箱，而是使用了四个更小、更快的并行工作存储箱，使数据能够无需排队即可流经系统。他们还用一种巧妙的、无需乘法的技巧取代了沉重的清理步骤，该技巧仅使用简单的加法和倍增，节省了大量的空间和功耗。通过将这些内存技巧与高度优化的“蝴蝶”单元（执行实际数学运算的微型计算器）相结合，他们创造出了一个既极其快速又出奇精巧的设计。当他们在现场可编程逻辑门阵列（FPGA）——一种可以被重新编程以充当定制硬件的芯片——上测试他们的创造物时，他们发现其效率显著高于目前文献中的任何其他设计。具体而言，他们的设计实现的“面积-时间乘积”（衡量芯片完成一项工作所需的空间和时间的指标）比最节省空间的方案好 2.67 倍，比最快速的高速设计好 1.48 倍。其结果是一个多功能、可扩展的引擎，它可以帮助我们在不牺牲成本或电池寿命的前提下，保障我们的数字未来免受量子威胁。

技术摘要：PIP-NTT：一种面向 PQC 中迭代 NTT 的可扩展存储并行化加速器

问题陈述
基于格的后量子密码学（PQC），特别是 NIST 标准化的 ML-KEM (Kyore) 和 ML-DSA (Dilithium)，高度依赖于数论变换（NTT）来实现高效的多项式乘法。现有的迭代 NTT 硬件加速器在吞吐量与资源利用率之间面临权衡。高吞吐量设计通常采用深层流水线和大容量存储阵列或多个蝴蝶单元，这会产生不适合资源受限平台的巨大面积开销。相反，面向面积优化的设计通常依赖于“乒乓”存储方案和单蝴蝶单元。虽然这些设计减少了硬件足迹，但本质上限制了可扩展性、并行性和频率优化，从而造成性能瓶颈。此外，逆向 NTT (INTT) 后所需的重缩放（rescaling）步骤通常涉及代价高昂的模乘法或除法，增加了关键路径延迟。

方法论
作者提出了 “PIP-NTT”，一种统一的、流水线化且存储并行的 NTT 加速器，旨在平衡面积效率与计算吞吐量。该方法基于三项核心创新：

统一流水线蝴蝶单元 (DSE)： 作者对 Cooley–Tukey (CT) 和 Gentleman–Sande (GS) 蝴蝶单元进行了全面的设计空间探索 (DSE)。他们评估了包括非流水线基准设计在内的八种架构变体，涵盖了利用粗粒度和细粒度流水线的不同设计。最优设计——即 8 级流水线蝴蝶单元 (8SP-BU)——集成了模约减（使用 Barrett 方法）和算术运算，并通过在数据路径中策略性地放置寄存器，在最大化工作频率的同时最小化面积开销。
无乘法重缩放： 对于 INTT 重缩放步骤 ( $a \cdot n^{-1} \mod q$ )，作者利用了 Kyber 模数 ( $q=3329$ ) 的特定同余特性，其中 $n^{-1} \equiv -13 \pmod{3329}$ 。他们没有使用复杂的移位-加法电路或除法，而是实现了一种轻量级架构，通过模倍增和加法来计算 $13a$ ，随后进行条件取负。这消除了在该步骤中使用通用乘法器的需求。
存储并行化策略： 为了克服传统乒乓存储方案的局限性而不增加总存储容量，作者引入了一种使用四个较小存储块（每个大小为 $n/4$ ）而非两个较大块的技术。系数存储在相邻对中。基于多路复用器的交换网络根据当前阶段的偏移量 ( $\delta$ ) 对输出进行重排序。这使得两个蝴蝶单元可以同时运行。当偏移量较大时 ( $\delta \ge n/4$ )，系统利用全部四个存储块和两个蝴蝶单元；当偏移量较小时 ( $\delta < n/4$ )，系统实现部分并行，使用两个活跃块。该策略在保持相同总存储容量的前提下，将时钟周期减半，相比于单单元迭代设计。

主要贡献

优化的蝴蝶架构： 一种统一的 CT/GS 蝴蝶单元，通过细粒度流水线将频率从 46 MHz（基准）提升至 298 MHz，而面积开销仅增加 1.32 倍。
高效重缩放： 一种用于 INTT 重缩放的无乘法架构，与标准的 7 项移位-加法实现相比，减少了 1.67 倍的 Slice 使用量和 1.84 倍的 LUT 使用量。
可扩展存储并行性： 一种使用四个 $n/4$ 大小的存储块和交换网络的创新存储组织方式，通过在迭代 NTT 中实现部分并行，在不增加总存储成本的情况下减少了 50% 的时钟周期。
集成加速器 (PIP-NTT)： 一个完整的 FPGA 实现，集成了两个优化的蝴蝶单元和存储并行化方案，支持 Kyber 参数 ( $n=256, q=3329$ ) 的正向 (FNTT) 和逆向 (INTT) 变换。

实验结果
PIP-NTT 设计在 Xilinx Virtex-7 和 Artix-7 FPGA 平台上进行了实现。

性能： 该加速器运行频率为 200 MHz，计算单个 FNTT 或 INTT 需要 2.60 µs（520 个时钟周期）。
效率： 在面积-时间乘积 (ATP) 方面，PIP-NTT 实现了：
- 与文献中最优化的面积型 NTT 加速器相比，效率提高了 2.67 倍。
- 与最高速 NTT 加速器相比，效率提高了 1.48 倍。
资源使用： 该设计在 Virtex-7 上使用了 156 个 Slice、426 个 LUT 和 379 个 Flip-Flop，展示了相对于其吞吐量而言极其紧凑的足迹。

意义与主张
论文声称 PIP-NTT 为未来的加密硬件提供了一种通用的解决方案，有效地解决了迭代 NTT 设计中固有的可扩展性与效率权衡问题。通过提出的存储并行化策略，PIP-NTT 将并行度与总存储成本解耦，从而在严格的面积约束下实现了高吞吐量。作者强调，该架构并不局限于 Kyber；其存储策略的基数无关性（radix-agnostic）以及内存模块的模块化设计，使其能够以极小的修改适配到其他 PQC 方案（如 Dilithium）及变化的环大小。该工作将 PIP-NTT 定位为一种平衡且资源高效的方法，适用于从嵌入式系统到数据中心等多种部署场景。

类似论文