💻 computer science

GPU Acceleration of Learning With Errors KEMs Using OpenACC for Post-Quantum Cryptography

本文提出了一种基于 OpenACC 的加速学习误差（LWE）密钥封装机制的 GPU 加速实现，证明了与传统的 CPU 和基于 H100 的系统相比，该实现在 NVIDIA GPU（尤其是 Grace Hopper 超级芯片）上实现了显著的加速（高达 208 倍）并提高了能量效率。

原作者： Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

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

想象一下，你正试图用一把极其复杂的钥匙锁上一个宝箱，这把钥匙复杂到连来自未来的超级智能机器人（量子计算机）都无法破解。这就是后量子密码学（Post-Quantum Cryptography）的目标。这篇论文所关注的特定“锁”被称为容错学习（Learning With Errors, LWE）。

把 LWE 想象成试图解决一个巨大的数学谜题，而有人故意在信号中加入了一些“静电”或“噪声”。制造噪声很容易，但如果没有密钥，想要从噪声中过滤出原始信息却极其困难。问题在于，用标准计算机来解这个谜题就像是一粒一粒地搬运沙子来移动一座大山——这需要耗费无穷长的时间。

以下是研究人员为了提高效率所做的工作，用简单的语言解释如下：

1. 问题所在：CPU 是慢速卡车

作者从一种在标准计算机处理器（CPU）上运行的版本开始。他们发现 CPU 显得力不从心。这就像是一辆单辆货运卡车试图搬运数千个箱子。每当它需要从仓库（内存）向卡车车厢搬运一个箱子（一段数据）时，它都必须停下来、装载、然后行驶。卡车大部分时间都在等待，而不是在工作。

2. 解决方案：GPU 是无人机机队

为了解决这个问题，他们将繁重的工作交给了 GPU（图形处理器）。如果 CPU 是单辆货运卡车，那么 GPU 就是一支由数千架超快速小型无人机组成的机队。

类比： 与其让一辆卡车一次运一个箱子，不如让 GPU 同时运送数千个箱子。
工具： 他们使用了一种叫做 OpenACC 的编程语言。你可以把它看作是一个通用遥控器。他们并没有重写整个无人机的操作手册（因为那既困难又容易出错），而是直接对着现有的卡车指令指向了遥控器并说：“嘿，你也做这个部分，但要更快一点！”这使得他们在升级软件时，无需破坏原有系统即可轻松完成。

3. 瓶颈： “噪声”生成器

在这种加密过程中，你需要大量的随机“噪声”来增加谜题的难度。

旧方法： CPU 生成噪声，将其记录下来，然后将其运送到 GPU。这就像卡车司机停下来写购物清单，然后开车去商店，买好东西再开车回来。这浪费了大量时间。
改进方法： 他们直接在 GPU 的仓库内部安装了一个“噪声生成器”。现在，无人机可以在现场生成自己的随机噪声。它们不再需要等待卡车运送物资。这极大地减少了等待时间。

4. “批处理”技巧

加密过程涉及同时解决 256 个微型谜题（对应于信息的每一位）。

旧方法： GPU 解决一个谜题，停止，等待指令，再解决下一个，停止，等待……就像厨师一次只煎一个蛋，并在每个蛋之间等待炉灶冷却一样。
改进方法： 他们使用了一种称为 算内批处理（Intra-Operation Batching） 的策略。这就像厨师一次性把 256 个蛋都放在一个大锅里同时烹饪。GPU 进行一次大规模的“启动”来同时解决所有 256 个谜题，从而节省了大量时间。

5. 结果：速度与能量

研究人员在不同类型的超快速计算机（GPU）上测试了这种方法，并将其与旧的 CPU 方法进行了比较。

速度： 在他们测试的最先进、功能最强大的计算机（Grace Hopper 超级芯片）上，他们的新方法比旧的 CPU 方法快了 208 倍。
- 类比： 如果旧卡车送达包裹需要 3 小时，那么新的无人机机队只需不到一分钟。
- 他们甚至能够处理规模如此之大的谜题，以至于旧的 CPU 会因为内存耗尽而崩溃。
能量： 新方法也使用了更少的能量。完成同样的工作，Grace Hopper 计算机消耗的能量大约只有使用另一种类型快速 GPU 的标准计算机的一半。
- 类比： 这就像是用混合动力汽车代替耗油的卡车来完成同样的交付任务。

6. 为什么这很重要

这篇论文表明，通过使用这些“无人机”（GPU）以及智能管理技巧（OpenACC、批处理和设备端噪声），我们可以使这些超安全、具备量子防御能力的锁变得实用。如果没有这些加速，这些数学运算太慢了，在现实世界中根本无法应用。有了这些技术，我们可以在不需要为等待一个锁扣合而等待数天的情况下，保护我们的数据免受未来量子计算机的威胁。

简而言之： 他们将一种缓慢、沉重的加密方法，通过使用数千个协同工作的微型工人（GPU）、让他们自行生成供应物资、并停止等待指令，实现了巨大的提速。结果是，该系统比以前快了数百倍，并且更加节能高效。

技术摘要：使用 OpenACC 加速基于误差的学习（LWE）密钥封装机制（KEM）

问题陈述
大规模量子计算机的出现通过 Shor 算法威胁着当前的非对称加密协议（如 RSA、ECC）。后量子密码学（PQC）已成为一种解决方案，其中基于误差的学习（LWE）问题的格密码方案（特别是其相关的密钥封装机制 KEM）处于核心地位。然而，基于 LWE 的方案由于大规模矩阵运算和随机数生成的存在，引入了显著的计算开销，这往往使得它们在标准 CPU 架构上的高吞吐量服务器应用中变得难以实现。虽然 GPU 加速已被用于 PQC 研究，但现有的大多数实现依赖于特定于 CUDA 的优化，限制了可移植性和开发效率。此外，简单的移植往往无法解决诸如主机-设备内存传输延迟和随机数生成序列化等瓶颈问题。

方法论
作者提出了一种基于“纯” LWE（避免使用 Ring-LWE 等额外代数结构）的密钥封装机制（KEM），并开发了一个使用 OpenACC 指令驱动编程模型的 GPU 导向实现。该工作通过以下方法论步骤进行：

基准实现： 一个使用 OpenMP 在多核 CPU 上进行并行化的 C++ LWE-KEM 实现。该方案利用 Fujisaki-Okamoto (FO) 变换来实现 IND-CCA2 安全性，涉及密钥生成（KeyGen）、封装（Encaps）和解封装（Decaps）阶段。
OpenACC 移植与优化： 使用 OpenACC 将 CPU 代码移植到 GPU。为了克服性能瓶颈，作者实施了三种主要策略：
- 算子内批处理（Intra-Operation Batching）： 不同于顺序处理 256 个独立的比特消息（这会触发多次内核启动和内存传输），该实现将所有 256 次加密合并为单次 GPU 内核启动。这暴露了细粒度的并行性（ $256 \times n$ 个工作项）并摊薄了调用开销。
- 设备驻留随机数生成（Device-Resident RNG）： 意识到通过 PCIe 传输随机噪声向量会产生严重的瓶颈，作者集成了 RNGonGPU 库。该库在 GPU 上直接实现了 AES-256 确定性随机比特生成器（DRBG）。仅需从主机传输一个 64 位种子到设备，与传输预生成的噪声向量相比，将数据传输量减少了约六个数量级。
- 显式数据管理： 作者没有使用 CUDA 统一内存，而是采用了显式的 enter data 和 exit data 指令来确定性地控制主机-设备传输，从而最大限度地减少不必要的通信，并确保仅在特定的同步点（例如哈希计算前）保持数据一致性。
内核并行化： 矩阵-向量乘法是主要的计算成本，通过分层并行化处理。对于加密/解密过程，独立的加密任务被分配给 OpenACC 线程组（gangs），而密文组件则在向量车道（lanes）上并发计算。

核心贡献

开源实现： 作者提供了一个针对 CPU（OpenMP）和 GPU（OpenACC）的纯 LWE 基础 KEM 开源实现，以实现可重复的基准测试。
指令驱动优化： 一套适用于广泛 LWE 方案的 GPU 导向优化方法，证明了指令驱动模型（OpenACC）可以在无需深厚 CUDA 专业知识的情况下实现高性能。
全面评估： 对多个 NVIDIA GPU 代际（Volta、Ampere、Hopper）以及架构（x86 + Hopper 与基于 ARM 的 Grace Hopper 超级芯片）进行了性能、能效和可扩展性的详细研究。

结果
评估在包括 NVIDIA GH200 Grace Hopper 超级芯片、A100 和 V100S 在内的多种平台上进行。

加速比： 优化的 OpenACC 实现相对于多线程 CPU 基准实现了显著加速。在 GH200 平台上，对于大问题规模（ $n=4096$ ），加速比高达 208×。当 $n \ge 256$ 时，GPU 实现开始超越 CPU 基准。
可扩展性： 随着问题规模的增加，GPU 实现表现出比 CPU 版本更优越的可扩展性，能够有效处理由于内存竞争和同步开销导致在 CPU 上难以处理的参数集（例如 $n=32768$ ）。
能效： 在 GH200 超级芯片上，与 x86 + H100 系统相比，该实现实现了 1.78× 的解题能耗（energy-to-solution）降低，这主要归功于基于 ARM 的 Grace CPU 较低的功耗。GH200 相较于 x86+Hopper 的解题时间改善较为温和（1.19×）。
架构缩放： 跨代分析（V100S $\to$ A100 $\to$ GH200）表明，性能缩放主要由高带宽内存（HBM）带宽驱动。然而，随着带宽的增加，按需生成矩阵元素（算术成本）和固定 CPU 端 FO 变换成本的相对开销开始限制缩放，使瓶颈从纯内存受限转向计算与同步约束并存的状态。
优化影响： 分析显示，原始实现受限于主机端计算和 PCIe 传输（GPU 饥饿）。优化后的实现将瓶颈转移到了同步环节，GPU 活动在迭代时间中维持在 ~98%。

意义
论文声称其结果强调了 GPU 加速对于计算密集型 LWE 基础密码学工作负载的有效性。通过利用 OpenACC，作者展示了一条平衡可编程性与性能的高性能 PQC 路径，避免了对底层 CUDA 编码的需求。该研究表明，通过适当的优化（特别是算子内批处理和设备驻留 RNG），“纯” LWE 方案（虽然提供保守的安全假设但计算成本较高）可以在现代异构平台上变得实用。该研究还强调了协同优化整个异构流水线的重要性，因为在下一代架构中，CPU 端操作和互连技术正日益成为限制扩展性的因素。未来的工作建议将此方法扩展到多 GPU 环境和其他加速器架构（AMD、Intel）。