Implementation and Optimization of HQC Decoding on NPU-Integrated Devices

以下是关于论文《Implementation and Optimization of HQC Decoding on NPU-Integrated Devices》（集成 NPU 设备上的 HQC 解码实现与优化）的技术摘要。

问题陈述

Hamming Quasi-Cyclic (HQC) 已被 NIST 选中，作为一种基于代码的密钥封装机制 (KEM)，旨在为基于格的后量子密码学提供算法多样性。虽然 HQC 依赖于纠错码（具体为级联的 Reed-Muller 和 Reed-Solomon 码）来保证安全性，但其在移动和嵌入式平台上的实际部署受到了高昂解码计算成本的阻碍。

现有的在受限 CPU 或专用硬件（如 FPGA、RISC-V）上的实现表明，HQC 的性能高度依赖于如何将解码内核映射到执行后端。然而，现代移动平台越来越多地集成具有向量加速器（如 Qualcomm 的 Hexagon Vector eXtensions，简称 HVX）的神经网络处理单元 (NPU)，这些加速器主要设计用于 AI 和信号处理。本研究解决的挑战在于，HQC 解码无法通过将标量解码器直接翻译为这些向量后端来实现高效加速。解码过程涉及复杂的依赖关系、特定的平局决胜规则（tie-breaking rules）以及不规则的内存访问模式（例如在加法 FFT 中），这些特性与 SIMD 风格的向量执行并不自然契合。

方法论

作者提出了一种针对集成 NPU 的 Qualcomm 设备上的 Hexagon/HVX 向量后端进行端到端优化的 HQC 解码实现。该工作并非使用张量推理引擎，而是专注于向量执行模型，该模型支持宽 SIMD 操作、逐通道算术运算和归约（reduction）。

该方法论包括将 HQC 解码器分解为其组成的 Reed-Muller（内码）和 Reed-Solomon（外码）组件，并重新设计主导内核，使其符合 HVX 友好的数据布局和执行模式：

1. Reed-Muller 解码优化：

   • 向量化 Hadamard 变换： 作者重新设计了用于内层重复 Reed-Muller 码的快速 Hadamard 变换。他们利用 HVX 指令集（如 VDEALH、VADDH、VSUBH）执行并行逐通道加法和减法，取代了标量实现中的顺序蝴蝶变换阶段。
   • 等效标量的峰值选择： 一个关键挑战是保留标量解码器的平局决胜规则（即在系数最大模相等时选择最小索引）。作者实现了一种向量化搜索，用于计算模值、识别所有峰值候选者，并在候选索引上执行向量最小值归约，以确保与标量参考实现具有位级等价性。

2. Reed-Solomon 解码优化：

   • 面向 HVX 的有限域算术： 对于向量化操作（综合征计算和 Chien 搜索），作者使用基于 xtime 原语的位串行 Horner 方法取代了表驱动的标量乘法。这使得可以在 HVX 通道中进行标量与向量的乘法，而无需依赖会导致缓存缺失或复杂索引的大型查找表。
   • 向量化综合征计算： 实现不再顺序计算综合征，而是将原根的幂次打包进向量，并通过跨所有综合征索引的 XOR 操作同时累积结果。
   • 缩短支持集的 Chien 搜索： 意识到标量实现中使用的加法 FFT 具有不适合 HVX 的顺序依赖性，作者使用缩短支持集的 Chien 搜索取代了它。该方法在保持多项式系数顺序性的同时，利用打包向量在公共支持点上评估误差定位多项式，从而实现跨 HVX 通道的并行评估。
   • Berlekamp-Massey 处理： 误差定位多项式的计算（Berlekamp-Massey 算法）本质上是顺序的且长度较短（对于 HQC-128 最多 16 个系数）。作者保留了这一阶段的标量执行，但使用表驱动的对数/反对数方法优化了其有限域乘法，因为对于如此短的循环，向量化收益很小。

3. 系统集成：

   • 该实现运行在配备 Snapdragon 8 Gen 2 的开发套件上，通过 FastRPC 接口将任务从主机 CPU 卸载到 cDSP (Hexagon DSP)。
   • 为了减轻 FastRPC 初始化的高昂开销（约 557 µs），作者采用了批处理策略，在单次远程调用中处理多个解码实例，以摊销通信成本。

核心贡献

• 确定了向量适用性： 本文确立了由于可靠性向量、Hadamard 系数和综合征向量固有的向量结构，HQC 解销是 Hexagon/HVX 加速的天然候选对象。
• 内核重构： 作者提出了对主导解码内核的完整重新设计：
  • 向量化的 Reed-Muller Hadamard 变换和峰值选择，严格保留了标量平局决胜规则。
  • 面向 HVX 的有限域乘法和综合征计算。
  • 替代标量加法 FFT 的向量化缩短支持集 Chien 搜索。
• 性能评估： 该工作通过精确周期的 Hexagon 模拟器和在 Snapdragon 8 Gen 2 真机上的实验进行了全面的评估。
• 可扩展性： 优化原则展示了从 HQC-128 到 HQC-192 和 HQC-256 的扩展能力，仅需针对块大小和更大支持集的处理进行调整。

结果

评估结果显示了在延迟、能效和主机 CPU 卸载方面的显著提升：

• 模拟器结果 (HQC-128)： 优化后的实现将每次解码的成本从 953,763 降至 41,471 Pcycles，代表了 23.00 倍的加速和 95.7% 的处理器周期减少。子阶段分析显示了巨大的收益，例如将 Reed-Muller Hadamard 变换从 263,175 降至 17,950 Pcycles。
• 真机结果 (Snapdragon 8 Gen 2)：
  • 延迟： 与 ARM CPU 标量基准相比，支持 NPU 的批处理后端实现了 2.07× (HQC-128)、1.85× (HQC-192) 和 1.96× (HQC-256) 的延迟加速。
  • 能效： 该实现将能效提高了 18.13× (HQC-128)、11.77× (HQC-192) 和 16.81× (HQC-256)。
  • CPU 卸载： 每次解码的主机 CPU 时间减少了 99.0%–99.7%，在解码运行于 cDSP 时，有效地释放了应用处理器以处理其他任务。
• 开销说明： 作者指出 FastRPC 边界成本显著（每次调用约 531–553 µs）。报告的真机增益是通过将多个解码批处理到单次调用中实现的；若采用“一解码一调用”的方法，由于该开销，速度会慢 5.4 倍至 15 倍。

意义与声明

本文声称，只要底层内核围绕现有的向量执行模型进行重构，集成 NPU 的移动平台可以作为结构化后量子密码学解码的有效后端。

• 算法多样性： 这项工作通过证明像 HQC 这样的基于代码的方案也可以在现代移动硬件上高效部署（而不只是基于格的方案），支持了 NIST 的多样性目标。
• 硬件利用： 它强调了通常用于 AI 的向量加速器 (HVX) 非常适合具有规则数据结构的密码原语，为在无需专用加密硬件的情况下，在消费级设备上实现高效的后量子安全提供了路径。
• 关于安全性的审慎说明： 作者明确指出，目前的实现并非恒定时间 (constant-time)。他们承认使用表驱动有限域算术和具有分支逻辑的 Berlekamp-Massey 逻辑可能会引入潜在的侧信道漏洞（计时和功耗）。他们将其定义为以性能为中心的优化，并将开发完全恒定时间、具备侧信道抗性的后端作为未来的工作方向。
• 未来工作： 作者指出，将这些解码优化与加速稀疏多项式乘法（HQC 解封装中的另一个主要成本）相结合，是实现全解封装加速的下一个逻辑步骤。