Implementation and Optimization of HQC Decoding on NPU-Integrated Devices

Problem Statement

Hamming Quasi-Cyclic (HQC) has been selected by NIST as a code-based Key Encapsulation Mechanism (KEM) to provide algorithmic diversity alongside lattice-based post-quantum cryptography. While HQC relies on error-correcting codes (specifically concatenated Reed-Muller and Reed-Solomon codes) for security, its practical deployment on mobile and embedded platforms is hindered by the high computational cost of its decoding procedure.

Existing implementations on constrained CPUs or specialized hardware (FPGAs, RISC-V) have shown that HQC performance is heavily dependent on how decoding kernels are mapped to the execution backend. However, modern mobile platforms increasingly integrate Neural Processing Units (NPUs) with vector accelerators (such as Qualcomm's Hexagon Vector eXtensions, or HVX) designed primarily for AI and signal processing. The challenge addressed in this work is that HQC decoding cannot be efficiently accelerated by a direct translation of scalar decoders to these vector backends. The decoding process involves complex data dependencies, specific tie-breaking rules, and irregular memory access patterns (e.g., in additive FFTs) that do not naturally align with SIMD-style vector execution.

Methodology

The authors propose an end-to-end optimized HQC decoding implementation targeting the Hexagon/HVX vector backend on NPU-integrated Qualcomm devices. Rather than using a tensor-inference engine, the work focuses on the vector execution model, which supports wide SIMD operations, lane-wise arithmetic, and reductions.

The methodology involves decomposing the HQC decoder into its constituent Reed-Muller (inner) and Reed-Solomon (outer) components and redesigning the dominant kernels to fit HVX-friendly data layouts and execution patterns:

1. Reed-Muller Decoding Optimization:

   • Vectorized Hadamard Transform: The authors redesign the fast Hadamard transform for the inner duplicated Reed-Muller code. They utilize HVX intrinsics (e.g., VDEALH, VADDH, VSUBH) to perform parallel lane-wise additions and subtractions, replacing the sequential butterfly stages of the scalar implementation.
   • Scalar-Equivalent Peak Selection: A critical challenge is preserving the scalar decoder's tie-breaking rule (selecting the smallest index among coefficients with equal maximum magnitude). The authors implement a vectorized search that computes magnitudes, identifies all peak candidates, and performs a vector minimum reduction on candidate indices to ensure bit-level equivalence with the scalar reference.

2. Reed-Solomon Decoding Optimization:

   • HVX-Oriented Finite-Field Arithmetic: For vectorized operations (syndrome computation and Chien search), the authors replace table-driven scalar multiplication with a bit-serial Horner method using xtime primitives. This allows for scalar-by-vector multiplication across HVX lanes without relying on large lookup tables that would cause cache misses or require complex indexing.
   • Vectorized Syndrome Computation: Instead of computing syndromes sequentially, the implementation packs powers of the primitive element into vectors and accumulates results via XOR operations across all syndrome indices simultaneously.
   • Shortened-Support Chien Search: Recognizing that the additive FFT used in scalar implementations has sequential dependencies unsuitable for HVX, the authors replace it with a shortened-support Chien search. This method evaluates the error-locator polynomial over public support points using packed vectors, allowing parallel evaluation across HVX lanes while maintaining the sequential nature of the polynomial coefficients.
   • Berlekamp-Massey Handling: The error-locator polynomial computation (Berlekamp-Massey algorithm) is inherently sequential and short (max 16 coefficients for HQC-128). The authors keep this stage scalar but optimize its finite-field multiplications using table-driven logarithm/antilogarithm methods, as vectorization yields little benefit for such short loops.

3. System Integration:

   • The implementation runs on a Snapdragon 8 Gen 2 development kit using the FastRPC interface to offload tasks from the host CPU to the cDSP (Hexagon DSP).
   • To mitigate the high overhead of FastRPC initialization (approx. 557 µs), the authors employ a batching strategy, processing multiple decoding instances in a single remote call to amortize the communication cost.

Key Contributions

• Identification of Vector Suitability: The paper establishes that HQC decoding is a natural candidate for Hexagon/HVX acceleration due to the inherent vector structure of its reliability vectors, Hadamard coefficients, and syndrome vectors.
• Kernel Redesign: The authors present a complete redesign of the dominant decoding kernels:
  • A vectorized Reed-Muller Hadamard transform and peak selection that strictly preserves scalar tie-breaking rules.
  • HVX-oriented finite-field multiplication and syndrome computation.
  • A vectorized shortened-support Chien search that replaces the scalar additive FFT.
• Performance Evaluation: The work provides a comprehensive evaluation using both the cycle-accurate Hexagon simulator and real-device experiments on a Snapdragon 8 Gen 2.
• Scalability: The optimization principles are demonstrated to extend from HQC-128 to HQC-192 and HQC-256, with adjustments for block sizes and multi-vector accumulation for larger support sets.

Results

The evaluation demonstrates substantial improvements in latency, energy efficiency, and host CPU offloading:

• Simulator Results (HQC-128): The optimized implementation reduces the decoding cost from 953,763 to 41,471 Pcycles per decode, representing a 23.00× speedup and a 95.7% reduction in processor cycles. Substage analysis shows massive gains, such as reducing the Reed-Muller Hadamard transform from 263,175 to 17,950 Pcycles.
• Real-Device Results (Snapdragon 8 Gen 2):
  • Latency: The batched NPU-supported backend achieves latency speedups of 2.07× (HQC-128), 1.85× (HQC-192), and 1.96× (HQC-256) compared to the ARM CPU scalar baseline.
  • Energy Efficiency: The implementation improves energy efficiency by 18.13× (HQC-128), 11.77× (HQC-192), and 16.81× (HQC-256).
  • CPU Offloading: The host CPU time per decode is reduced by 99.0%–99.7%, effectively freeing the application processor for other tasks while the decoding runs on the cDSP.
• Overhead Note: The authors note that the FastRPC boundary cost is significant (~531–553 µs per call). The reported real-device gains are achieved specifically through batching multiple decodes into a single call; a "one-decode-per-call" approach would be significantly slower (5.4× to 15× slower) due to this overhead.

Significance and Claims

The paper claims that NPU-integrated mobile platforms can serve as effective backends for structured post-quantum cryptographic decoding, provided the underlying kernels are reformulated around the available vector execution model.

• Algorithmic Diversity: The work supports the NIST goal of cryptographic diversity by demonstrating that code-based schemes like HQC can be efficiently deployed on modern mobile hardware, not just lattice-based schemes.
• Hardware Utilization: It highlights that vector accelerators (HVX), often reserved for AI, are well-suited for cryptographic primitives with regular data structures, offering a path to efficient post-quantum security on consumer devices without requiring dedicated cryptographic hardware.
• Modesty on Security: The authors explicitly state that their current implementation is not constant-time. They acknowledge that the use of table-driven finite-field arithmetic and branchy Berlekamp-Massey logic introduces potential side-channel vulnerabilities (timing and power). They frame this as a performance-focused optimization, leaving the development of a fully constant-time, side-channel-resistant backend as future work.
• Future Work: The authors identify the integration of these decoding optimizations with accelerated sparse polynomial multiplication (the other major cost in HQC decapsulation) as the next logical step toward full decapsulation acceleration.