Implementation and Optimization of HQC Decoding on NPU-Integrated Devices Vu Minh Chau1 , Nguyen Ngoc Kiet1 , Pham Quang Minh1 , Mai Xuan Ngoc1 , Nguyen Duc Anh1 , and Hoang Ta∗1
arXiv:2606.01968v1 [cs.CR] 1 Jun 2026
1
School of Information and Communication Technology, Hanoi University of Science and Technology, Vietnam
Abstract Hamming Quasi-Cyclic (HQC) has been selected by NIST for standardization as an additional code-based key-encapsulation mechanism, providing algorithmic diversity alongside lattice-based postquantum cryptography. Efficient deployment of HQC on mobile and embedded platforms, however, requires careful optimization of its decoding procedure, whose Reed-Muller and Reed-Solomon components dominate the computational cost. This paper studies HQC decoding on Qualcomm Hexagon processors in NPU-integrated devices, focusing on the Hexagon Vector eXtensions (HVX) backend rather than a tensor-inference engine. We observe that HQC decoding naturally exposes vectorstructured computation, including Reed-Muller reliability vectors, Hadamard-transform coefficients, Reed-Solomon syndrome vectors, finite-field products, and packed support-point evaluations. Based on this observation, we redesign the dominant decoding kernels around HVX-friendly data layouts and execution patterns, including a vectorized Reed-Muller Hadamard transform, scalar-equivalent peak selection, HVX-oriented finite-field arithmetic, vectorized syndrome computation, and shortenedsupport locator-root evaluation. We implement and evaluate the optimized decoder using both Hexagon simulator measurements and real-device experiments on a Snapdragon 8 Gen 2 hardware development kit. The results show that Hexagon/HVX-assisted decoding substantially reduces latency and energy consumption, improving energy efficiency by up to 18.13× while significantly offloading host CPU work. These results indicate that NPU-integrated mobile platforms can serve as effective backends for structured post-quantum cryptographic decoding when the underlying kernels are reformulated around vector execution.
1
Introduction
Post-quantum cryptography has been widely studied in recent years, since classical public-key cryptographic primitives based on integer factorization and discrete logarithms are vulnerable to large-scale quantum attacks [1]. In response to this long-term security concern, the U.S. National Institute of Standards and Technology (NIST) initiated a process to standardize quantum-resistant public-key cryptographic algorithms. Several families of cryptographic assumptions have been investigated as candidates for post-quantum security, including lattice-based, code-based, hash-based, multivariate-based, and isogeny-based assumptions. Among these, lattice-based cryptography has received particularly extensive attention and cryptanalytic study from the cryptographic community. As a result, two lattice-based constructions, namely the Module-Lattice-Based Digital Signature Algorithm (ML-DSA) and the Module-Lattice-Based KeyEncapsulation Mechanism (ML-KEM) [2, 3], were selected for standardization. In parallel, hash-based cryptography has also made substantial progress, with the Stateless Hash-Based Digital Signature Algorithm (SLH-DSA) [4] selected as a standardized stateless hash-based digital signature scheme. Beyond lattice-based and hash-based schemes, other post-quantum directions have also seen remarkable progress. In particular, code-based cryptography has recently gained further standardization momentum, with Hamming Quasi-Cyclic (HQC) [5, 6] selected by NIST for standardization as an additional code-based key-encapsulation mechanism to complement and diversify the key-establishment portfolio alongside MLKEM. Meanwhile, multivariate-based and isogeny-based signatures [7, 8, 9] continue to be evaluated in ∗ Corresponding author
1
NIST’s additional digital signature standardization process. These efforts emphasize the importance and urgency of cryptographic diversity, mitigating the risk of a single point of failure. HQC [6] relies on error-correcting codes and provides algorithmic diversity compared with lattice-based schemes. In essence, it employs a fixed concatenated code consisting of an outer Reed-Solomon code and an inner duplicated Reed-Muller code for error correction. As HQC has advanced toward standardization, recent studies have increasingly focused on its practical implementation, including software optimization, efficient finite-field arithmetic, and deployment on constrained or hardware-accelerated platforms [5, 10, 11, 12]. These works indicate that HQC performance is strongly influenced by how its decoding kernels are mapped to the target execution backend. Modern mobile and edge platforms increasingly integrate heterogeneous accelerators to support computationally intensive data-parallel workloads, including signal-processing and neural-network inference workloads [13]. These accelerator resources are commonly exposed as part of Neural Processing Unit (NPU) subsystems, which combine scalar, vector, and tensor-style execution units [14]. On Qualcomm platforms, the Hexagon processor provides Hexagon Vector eXtensions (HVX), which support wide SIMDstyle vector operations and enable efficient lane-wise arithmetic, comparisons, permutations, and reductions [15]. Although HVX is primarily designed for signal-processing and AI-oriented workloads, its vector execution model is also well suited to structured cryptographic kernels, especially those underlying codebased primitives. In this work, we study HQC decoding on Qualcomm Hexagon processors in NPU-integrated devices. More specifically, our optimized kernels target the Hexagon/HVX vector backend rather than a tensorinference engine. HQC decoding is a natural candidate for this execution model because its dominant Reed-Muller and Reed-Solomon kernels operate on vector-structured data, including Reed-Muller reliability vectors, Hadamard-transform coefficients, Reed-Solomon syndrome vectors, and packed finite-field support points. At the same time, these kernels cannot be accelerated efficiently by a direct translation of the scalar decoder: the Hadamard transform requires HVX-friendly data rearrangement, peak selection must preserve the scalar tie-breaking rule, and Reed-Solomon decoding requires vectorized finite-field arithmetic and support-point evaluation. We therefore decompose the HQC decoder into its Reed-Muller and Reed-Solomon components and redesign the dominant decoding kernels around HVX-friendly data layouts and execution patterns. The goal is not only to reduce processor-cycle counts, but also to improve energy efficiency and offload host CPU work on mobile and embedded platforms.
Contributions Our contributions are as follows. • We identify HQC decoding as a natural candidate for Hexagon/HVX acceleration on NPU-integrated mobile platforms. Its dominant Reed-Muller and Reed-Solomon decoding kernels operate on vectorstructured data, including reliability vectors, Hadamard-transform coefficients, syndrome vectors, finite-field elements, and packed support points. Based on this observation, we present an end-toend optimized HQC decoding implementation targeting the Hexagon/HVX vector backend. • We redesign the dominant decoding kernels around HVX-friendly data layouts and execution patterns. For the inner duplicated Reed-Muller code, we develop an HVX-friendly fast Hadamard transform and a vectorized peak-selection procedure that exactly preserves the scalar tie-breaking rule. For the outer Reed-Solomon stage, we introduce HVX-oriented finite-field multiplication, vectorized syndrome computation, and a shortened-support Chien search, namely a vectorized evaluation of the error-locator polynomial over the public shortened Reed-Solomon support points. In selected substage benchmarks, these optimizations reduce the Reed-Muller Hadamard transform from 263,175 to 17,950 Pcycles per decode, peak selection from 71,217 to 6,081 Pcycles, syndrome computation from 162,312 to 3,517 Pcycles, and the error-locator-polynomial-related stage from 119,595 to 6,581 Pcycles. • We evaluate the optimized decoder using both Hexagon simulator measurements and real-device experiments. In simulator measurements, the optimized implementation reduces the full HQC128 decoding cost from 953,763 to 41,471 Pcycles per decode, corresponding to a 23.00× speedup and a 95.7% reduction in Pcycles. On a Snapdragon 8 Gen 2 hardware development kit, the Hexagon/HVX-assisted implementation achieves 2.07×, 1.85×, and 1.96× latency speedups for HQC-128, HQC-192, and HQC-256, respectively; improves energy efficiency by 18.13×, 11.77×, and 16.81×; and reduces host CPU ms/decode by 99.0%–99.7% across all parameter sets.
2
Related Work HQC implementations on different hardware backends. Recent work has explored HQC implementation across a range of execution environments. On embedded CPUs, optimized HQC implementations on ARM Cortex-M4 platforms have been proposed to reduce the cost of polynomial multiplication and finite-field operations [11, 16]. On reconfigurable hardware, several works study HQC acceleration using FPGA and RTL designs. Deshpande et al. present a hand-optimized Verilog implementation of HQC key generation, encapsulation, and decapsulation [12], while later RTL accelerators provide unified support for HQC-128, HQC-192, and HQC-256 [17]. Other works target specific bottlenecks, such as sparse polynomial multiplication or Frobenius additive FFT-based multiplication on RISC-V/FPGA SoC platforms [18, 19]. These studies show that HQC performance strongly depends on the execution backend and the mapping of its algebraic kernels to hardware-friendly operations. Hardware acceleration of other post-quantum primitives. Beyond HQC, hardware-aware optimization has also been widely studied for other post-quantum cryptographic schemes. For lattice-based schemes, several works optimize Kyber/ML-KEM and Dilithium/ML-DSA on ARM Cortex-M4 by accelerating their number-theoretic transform and modular arithmetic kernels [20]. FPGA-based accelerators have also been developed for high-volume Kyber and Dilithium workloads, using parallelism and batch processing to improve throughput [21]. More recent hardware/software co-design efforts target opensource silicon platforms such as OpenTitan, where specialized big-number accelerators are used to speed up NTT-based PQC primitives [22]. Compared with these CPU, microcontroller, FPGA, and RISCV/SoC implementations, our work focuses on NPU-integrated Qualcomm platforms and studies how HQC decoding can be mapped to Hexagon/HVX vector operations to improve execution time, energy efficiency, and CPU offload. Organization. The remainder of this paper is organized as follows. Section 2 reviews the fundamental background on first-order Reed-Muller codes, Reed-Solomon codes, the HQC concatenated-code structure, and the NPU/HVX execution model used throughout the paper. Section 3 presents the proposed HQC decoding optimizations. Section 4 evaluates the proposed implementation using both Hexagon simulator measurements and real-device experiments, reporting latency, energy efficiency, and CPU-offloading benefits. Section 5 concludes the paper. Finally, Section A provides supplementary implementation details, including pseudocode for the main optimized kernels and the mapping between the abstract vector operations and Qualcomm Hexagon HVX intrinsics.
2
Preliminaries
We use the following notation throughout the paper. Let Z denote the ring of integers, and let F2 denote the binary finite field. For q = 28 , we write Fq for the finite field used by the Reed-Solomon component of HQC. For a positive integer m, let [m] = {1, . . . , m}. Vectors are denoted in boldface, e.g., x, and xi denotes the i-th coordinate of x.
2.1
First-Order Reed-Muller Code
Let m be a non-negative integer. The first-order Reed-Muller code of length 2m , denoted by RM(1, m), is defined as the set of evaluation vectors of all affine Boolean functions over Fm 2 . More precisely, X m RM(1, m) = f (x) x∈Fm : f (x) = b + ai xi (mod 2) ⊆ F22 . 2 i∈[m]
The parameters of RM(1, m) are n = 2m , k = m + 1, d = 2m−1 , where n is the code length, k is the dimension, and d is the minimum Hamming distance. Decoding first-order Reed-Muller codes can be performed efficiently using the fast Hadamard transform. Given a received vector y = (yx )x∈Fm , the 2 decoder first maps its binary entries to the bipolar representation zx = (−1)yx . For each a ∈ Fm 2 , it computes the correlation X W (a) = zx (−1)⟨a,x⟩ . x∈Fm 2
The decoder selects a value of a that maximizes |W (a)|. The sign of W (a) determines the affine offset, and the corresponding affine function is returned as the decoded codeword. 3
2.2
Reed-Solomon Code
Let R = Fq and let S = {α1 , . . . , αn } ⊆ R be a set of distinct evaluation points with n ≤ q. For a message polynomial m(X) ∈ Fq [X] satisfying deg(m) < k, the Reed-Solomon code of length n and dimension k is defined as RS(n, k) = m(α1 ), . . . , m(αn ) : m(X) ∈ Fq [X], deg(m) < k . Its minimum Hamming distance is d = n − k + 1. For decoding, let r = c + e be the received word, where c is the transmitted codeword and e is the error vector. The decoder first computes the syndrome values Sj = r(αj ),
j = 1, . . . , 2δ,
where α is a primitive element of Fq and δ is the error-correcting capability. In the cyclic or parity-check formulation used by the decoder, every valid codeword has zero syndrome at these check points. Hence, the syndromes depend only on the error polynomial e(X). If all syndromes are zero, then r is already a valid codeword. Otherwise, the decoder uses the syndrome sequence to solve the key equation and recover the errorlocator polynomial Y Λ(X) = (1 − Xαi ), i∈E
where E is the set of error positions. The roots of Λ(X) identify the error locations, and the corresponding error values are then recovered from the error-evaluator polynomial. Finally, these errors are subtracted from r to obtain the original codeword. Although Reed-Solomon codes are introduced above in the evaluation-code form, the HQC decoder uses a shortened cyclic/parity-check representation. In this representation, the received word is viewed Pn1 −1 as a polynomial r(X) = i=0 ri X i , and syndrome values are computed by evaluating this polynomial at the prescribed check points. Thus, valid codewords have zero syndromes at these check points.
2.3
Hamming Quasi-Cyclic (HQC)
HQC relies on a concatenated-code construction in which the inner and outer codes are Reed-Muller and Reed-Solomon codes, respectively. More precisely, HQC uses an outer code with parameters [ne , ke , de ] over Fq and an inner binary code with parameters [ni , ki , di ] over F2 , where q = 2ki . Each symbol of Fq is mapped bijectively to a codeword of the inner code, which induces a binary mapping Fnq e −→ FN 2 , where N = ne ni . Thus, the resulting binary concatenated code has parameters [N = ne ni , K = ke ki , D ≥ de di ]. HQC uses shortened Reed–Solomon codes together with duplicated Reed-Muller codes. The ReedMuller parameters used in the three HQC parameter sets are summarized in Table 1.
Instance HQC-128 HQC-192 HQC-256
Table 1: Duplicated Reed–Muller codes. Reed–Muller code Multiplicity Duplicated Reed–Muller code [128, 8, 64] 3 [384, 8, 192] [128, 8, 64] 5 [640, 8, 320] [128, 8, 64] 5 [640, 8, 320]
The multiplicity indicates how many times each Reed-Muller codeword is duplicated.
4
2.4
Neural Processing Unit (NPU)
In this work, the term refers to the data-parallel execution model exposed by vector accelerators such as Qualcomm Hexagon HVX [15]. Rather than describing the optimized decoder solely in terms of processor-specific instructions, we model the accelerator as a finite-lane vector machine. This abstraction is sufficient for the Reed-Muller and Reed-Solomon optimizations considered in this work, since their dominant operations consist of regular lane-wise arithmetic, finite-field products, permutations, and reductions. We mainly focus on the HQC-128 parameter set. The same optimization principles also apply to the other HQC parameter sets, with the corresponding changes in block sizes and the number of required vector blocks. Let L denote the number of lanes in a vector register, and let x = (x0 , . . . , xL−1 ) ∈ RL . The ring R depends on the stage being accelerated. Signed 16-bit integers are used for Reed-Muller soft values, whereas elements of F28 are embedded in 16-bit lanes for Reed-Solomon arithmetic. We use the following abstract vector operations: VADD(x, y) = (xi + yi )L−1 i=0 , VSUB(x, y) = (xi − yi )L−1 i=0 , VABS(x) = (|xi |)L−1 i=0 , VMAX(x, y) = (max(xi , yi ))L−1 i=0 , VMIN(x, y) = (min(xi , yi ))L−1 i=0 . The operation VSPLAT(a) = (a, . . . , a) broadcasts a scalar value to all vector lanes. We represent bit-level vector operations as VXOR(x, y) = (xi ⊕ yi )L−1 i=0 , VAND(x, y) = (xi ∧ yi )L−1 i=0 , VSHLs (x) = (xi ≪ s)L−1 i=0 , VSHRs (x) = (xi ≫ s)L−1 i=0 . We also use two reduction operations: VREDUCE_MAX(x) = max xi ,
VREDUCE_MIN(x) = min xi .
0≤i<L
0≤i<L
Both reductions are implemented as rotation trees. For example, maximum reduction applies updates of the form z ← VMAX z, VROTs (z) for a sequence of rotation offsets s. Replacing VMAX with VMIN gives the corresponding minimum reduction. Finally, the Reed–Muller transform uses the following selection primitives: L−1 VCMPEQ(x, y) = 1{xi = yi } i=0 , VSELECT(m, x, y) = (mi xi + (1 − mi )yi )L−1 i=0 . The complete mapping between the abstract vector operations and the corresponding Qualcomm Hexagon HVX intrinsics is provided in Section A.2.
3
Proposed Algorithms
3.1
Motivation and Challenges
HQC decoding is a natural candidate for acceleration on the Hexagon/HVX vector backend because its main computational objects have an inherent vector structure. In the Reed-Muller component, each duplicated block is first converted into a reliability vector and then processed by a Hadamard transform 5
whose butterfly stages consist of regular additions, subtractions, and data rearrangements. The summary of HQC decoding components is illustrated in Figure 1. In the Reed-Solomon component, syndrome values, finite-field products, and evaluations over the shortened support can also be organized as packed vectors. These structures match the lane-wise execution model of HVX and make it possible to exploit data-level parallelism beyond a scalar CPU implementation. At the same time, HQC decoding cannot be efficiently accelerated by a direct translation of the scalar decoder. For Reed-Muller decoding, the Hadamard transform requires an HVX-friendly memory layout and a careful sequence of vector rearrangements. Moreover, the final peak-selection step must preserve the scalar decoder’s tie-breaking rule, since different choices among equal-magnitude Hadamard coefficients may lead to different decoded outputs. Therefore, vectorization must preserve not only performance but also bit-level equivalence with the scalar reference behavior. The Reed-Solomon stage introduces a different set of challenges. Finite-field multiplication over F28 , syndrome computation, locator-root evaluation, and error-locator-polynomial updates involve a mixture of regular vector operations and scalar control logic. In particular, the additive-FFT-style root evaluation used in scalar implementations contains sequential dependencies and irregular memory-access patterns that are not well aligned with HVX execution. We therefore redesign the dominant Reed-Solomon kernels around HVX-oriented scalar-by-vector finite-field multiplication, vectorized syndrome computation and shortened-support Chien search. We describe the optimized implementation for the HQC-128 parameter set. The same optimization principles extend to HQC-192 and HQC-256, with changes in block sizes and the number of required vector blocks. Receive noisy codeword
Partition into Reed-Muller blocks
Decode each block with Reed-Muller (aggregate repetitions, Hadamard transform, peak selection)
Inner Reed-Muller decoding Form Reed-Solomon received word
Decode with Reed-Solomon (compute syndromes, recover locator, evaluate errors, correct word)
Outer Reed-Solomon decoding Recover message
Figure 1: Overview of the HQC decoding process.
Decoding vs. Full Decapsulation. HQC decapsulation proceeds in two stages: it first recovers a noisy codeword by combining the ciphertext with the secret key through a sparse polynomial multiplication, and then applies the concatenated decoder to that noisy codeword. This paper optimizes only the second stage—the decoding of the noisy codeword, i.e., the entry point of the pipeline in Figure 1. The polynomial-multiplication stage that produces the noisy codeword is a separate and comparably significant cost in HQC implementations, and has been the subject of dedicated accelerators, including sparse-polynomial multipliers [18] and Frobenius additive-FFT multipliers [19]; it is orthogonal to the 6
decoding kernels considered here. Accordingly, the speedups reported in this paper are for the decoding stage in isolation, not for end-to-end decapsulation. We focus on decoding because its Reed-Muller and Reed-Solomon kernels expose the non-obvious, control-flow-sensitive vectorization challenges (Hadamard data layout, scalar-equivalent tie-breaking, and locator-root evaluation), whereas the sparse polynomial multiplication is a regular shift-and-XOR pattern that maps directly onto the same HVX backend; integrating it is a natural next step toward full-decapsulation acceleration.
3.2
Reed-Muller Decoding
3.2.1
Repetition aggregation.
For each Reed-Solomon symbol, the duplicated Reed-Muller code provides several repetitions of a length128 Reed-Muller codeword. In HQC-128, the multiplicity is three. The decoder first aggregates the (r) repeated bits coordinate-wise. If bi ∈ {0, 1} denotes the i-th bit in repetition r, then the soft value used by the Hadamard decoder is 2 X (r) xi = bi , 0 ≤ i < 128. r=0
This produces an integer reliability vector that is subsequently used as the input to the Hadamard transform. For HQC-192 and HQC-256, the same aggregation procedure is used with multiplicity five. 3.2.2
Vector Hadamard transformation.
After expansion, the Reed-Muller decoder applies the fast Hadamard transform for RM(1, 7). The current vector is split into two paired parts x = xL ∥xR , then the decoder computes the lane-wise sum and difference, yL = xL + xR , yR = xL − xR , and concatenates them to form the next transform state y = yL ∥yR (Figure 2). We utilize the VDEALH intrinsic to split vector x before computing element-wise addition and subtraction in parallel using VADDH and VSUBH, respectively. The transform consists of seven butterfly stages for the 128-point Hadamard transform. The complete procedure is given in Algorithm 1.
b0
b0
b1
···
b1
···
b63
b63
b64
±
···
b126
b127
b64
···
b126
b127
Figure 2: Visual illustration of the butterfly operation with HVX support.
3.2.3
Vectorized peak selection with scalar-equivalent tie breaking.
The final Reed-Muller decision selects the Hadamard coefficient with the largest magnitude, breaking ties in favor of the smallest index: i⋆ = min arg max |x̂i |. i
The HVX implementation follows the same rule, but performs the search in parallel across all coefficient lanes. It first computes the magnitude vector m = (|x̂0 |, . . . , |x̂127 |), and reduces it to the global maximum magnitude M . All lanes satisfying |x̂i | = M are then marked as peak candidates. To enforce the scalar tie-breaking rule, the decoder keeps the original index of each candidate lane and replaces every non-candidate lane by a sentinel value larger than any valid index. Thus, the remaining problem becomes a vector minimum reduction over the candidate indices. The result is exactly the smallest index attaining the maximum magnitude. Finally, the sign of the selected coefficient x̂i⋆ determines the decoded Reed-Muller output bit. The detailed procedure is given in Algorithm 2. 7
3.3
Reed–Solomon Decoding
For HQC-128, the shortened Reed-Solomon code has length n1 = 46, message length k = 16, and errorcorrection parameter δ = 15. Given a received word c = (c0 , . . . , c45 ), the decoder computes 2δ = 30 syndromes, derives the error-locator polynomial σ(x), identifies its roots over the shortened support, computes error magnitudes, and corrects the received word [6]. 3.3.1
Galois field multiplication.
Reed-Solomon decoding involves several polynomial operations over F28 , where finite-field multiplication is one of the main costs. We use two multiplication strategies depending on the execution pattern: tabledriven multiplication for scalar operations, and an HVX-oriented bit-serial method when many products are computed in parallel. A. Table-driven multiplication. For scalar products, we use logarithm and antilogarithm tables. The antilogarithm table stores powers of the primitive element α, while the logarithm table maps each nonzero field element to its exponent with respect to α. Thus, instead of multiplying two field elements directly, we compute ( 0, a = 0 or b = 0, a·b= logα (a)+logα (b) mod 255 α , otherwise. This reduces one field multiplication to two logarithm lookups, one modular addition, and one antilogarithm lookup. B. Vector multiplication. For vectorized Reed-Solomon operations, i.e., syndrome computation and Chien search, we avoid table lookups and instead compute many field products in parallel using HVX lane-wise operations. The target operation is scalar-by-vector multiplication a · b = (ab0 , ab1 , . . . , abL−1 ),
a, bi ∈ F28 .
We first implement the lane-wise xtime operation, i.e., multiplication by X in F28 . In HQC, an overflow after a left shift is reduced by XORing with 0x1d. Thus, for each byte x, xtime(x) = (x ≪ 1) ⊕ (carry · 0x1d) & 0xff, where carry = (x ≫ 7) & 1. Using this xtime primitive, scalar-by-vector multiplication is performed in a bit-serial Horner form. Let a = (a, . . . , a), the bits of each lane bi are then processed from the most significant bit to the least significant bit. At bit position k, the implementation extracts the k-th bit of every lane, bk = (b ≫ k) & 1, turns it into a full-lane mask mk , updates the accumulator by xtime, and conditionally XORs in a: z ← xtime(z) ⊕ (a & mk ). After the eight bit positions are processed, each lane of z contains abi . The xtime and scalar vector multiplication procedures are given in Algorithm 3 and Algorithm 4, respectively. 3.3.2
Vectorized syndrome evaluation
Syndrome computation evaluates the received Reed-Solomon word at consecutive powers of the primitive element. Instead of computing one syndrome at a time, we vectorize across syndrome indices. For each received-symbol position j, we pack the required powers into aj = αj , α2j , . . . , α(2δ)j , 0, . . . , 0 ∈ F64 28 . The first 2δ lanes correspond to syndrome values, while the remaining lanes are padding. The decoder invokes the pre-described vector multiplication for each received symbol cj and aj to get the output: cj aj = (cj αj , cj α2j , . . . , cj α(2δ)j , 0, . . . , 0) and accumulates it by XOR: s ← s ⊕ cj aj . After all j ≥ 1 terms are processed, the constant term c0 is broadcast to all lanes and XORed into the accumulator: S = s ⊕ VSPLAT(c0 ). The first 2δ lanes of S form the syndrome array. 8
3.3.3
Shortened-support root search
Root finding identifies the positions where the error-locator polynomial vanishes on the Reed-Solomon support. For a candidate position i, let xi = α−i ,
0 ≤ i < n1 .
A position is marked as erroneous when the locator polynomial evaluates to zero at this point. The HQC specification describes this step using an additive FFT, which is well suited to scalar CPU implementations due to its asymptotically efficient polynomial evaluation structure. However, additive FFTs contain several sequential data dependencies and irregular memory-access patterns that limit their efficiency on HVX-style vector accelerators. Therefore, in our implementation, we instead use a shortenedsupport Chien search [23], whose evaluation pattern maps more naturally to lane-wise SIMD execution. In particular, we evaluate the locator polynomial only on the public support points of the shortened code. To expose vector parallelism, the powers of all support points are packed into vectors. For each degree j, we define 0 ≤ j ≤ δ, pj = (xj0 , xj1 , . . . , xjn1 −1 , 0, . . . , 0) ∈ F64 28 , where the remaining lanes are padded to match the HVX vector width. The locator polynomial is then evaluated by accumulating the coefficient-weighted support vectors, which are again computed efficiently with the help of scalar vector multiplication described above, using Q6_V_vxor_VV: r = σ0 p0 ⊕ σ1 p1 ⊕ · · · ⊕ σdeg σ pdeg σ . Equivalently, the i-th active lane of r contains σ(xi ). Lanes that evaluate to zero give the located-error indicator eloc 0 ≤ i < n1 . i = 1{σ(xi ) = 0}, Thus, the loop over the locator coefficients remains sequential, but for each coefficient all shortened support points are evaluated in parallel across HVX lanes. Figure 3 illustrates this procedure. p0 = (1, . . . , 1, 0, . . . , 0) σ0
⊗
1
···
1
0
···
0
p1 = (x0 , . . . , xn1 −1 , 0, . . . , 0) σ1
⊗
x0
.. . σd
⊗
xd 0
···
xn−1
d
d 0
···
xd n−1
.. . p = (x , . . . , x
0
···
0
d n1 −1 , 0, . . . , 0)
0
···
0
r = σ0 p0 ⊕ σ1 p1 ⊕ · · · ⊕ σd pd = σ(x0 ), . . . , σ(xn1 −1 ), 0, . . . , 0
lane-wise XOR accumulation
compare ri with 0 VCMPEQ(r, 0)
eloc = 1{r0 = 0}, 1{r1 = 0}, . . . , 1{rn1 −1 = 0}
root indicator / error-location mask
Figure 3: Vectorized shortened-support Chien search on packed support points, where d = deg σ.
3.3.4
Error-locator polynomial computation.
The error-locator polynomial σ(x) is recovered from the syndromes using the Berlekamp–Massey algorithm [24]. Over 2δ iterations, the algorithm maintains the current locator σ(x), an auxiliary (previousbest) locator b(x), and their degrees. At each iteration µ it (i) computes a discrepancy as the inner product of the current locator with the most recent syndromes, dµ = S µ ⊕
deg Mσ i=1
9
σi Sµ−i ,
and (ii) when dµ ̸= 0, updates the locator by σ(x) ← σ(x) ⊕ γ xm b(x), where γ = dµ · d−1 ρ and dρ is the discrepancy recorded at the last length change. Whenever the length-change condition 2 deg σ ≤ µ holds, the algorithm promotes the saved locator to the auxiliary polynomial b(x), resets the shift counter m, and updates the tracked degrees. Unlike the Reed-Muller stages and the syndrome and root-search kernels, the Berlekamp–Massey recurrence is inherently sequential: the discrepancy at iteration µ depends on the locator coefficients produced by the preceding iterations, and the locator and auxiliary polynomials are short—at most δ + 1 = 16 coefficients for HQC-128. Vectorizing this recurrence across HVX lanes therefore yields little benefit while complicating the control flow. We accordingly keep the error-locator stage scalar and instead accelerate its dominant cost—finite-field multiplication—using the table-driven logarithm/antilogarithm method of Section 3.3.1. Each locator update and each discrepancy term is a single F28 product reduced to two logarithm lookups, one modular addition, and one antilogarithm lookup; the outer recurrence runs the full 2δ = 30 iterations, while the inner discrepancy and update loops range only over the active coefficients up to the current locator degree. With table-driven arithmetic, this stage drops from 119,595 to 6,581 Pcycles per decode (Table 4)—about 16% of the optimized HQC-128 decode—without any HVX vectorization. The full procedure is given in Algorithm 6.
3.4
Extension to HQC-192 and HQC-256 Tweak Reed-Muller multiplicity RS Code Length Error Capacity Chien HVX vectors
HQC-128 3 46 15 1
HQC-192 5 56 16 1
HQC-256 5 90 29 2
Table 2: Extension to HQC-192 and HQC-256 Although the implementation discussion above mainly focuses on the HQC-128 parameter set, the same optimization strategy extends naturally to HQC-192 and HQC-256. The three HQC variants differ primarily in the number of Reed–Muller repetitions, Reed–Solomon code dimensions, and the resulting decoding workload. For HQC-192 and HQC-256, the Reed–Muller aggregation stage generalizes directly from multiplicity 3 to multiplicity 5. Instead of summing three duplicated Reed-Muller blocks before the Hadamard transform, the decoder accumulates five repeated blocks using the same lane-wise HVX addition operations. Since the Reed-Muller block size remains fixed at 128 bits, the Hadamard stages and peak-selection procedure remain unchanged; only the number of vector accumulation steps increases. The Reed–Solomon decoding stage also scales naturally to the larger parameter sets. In particular, HQC-256 increases the shortened Reed–Solomon support size to 90, which exceeds the 64 halfword lanes of a single HVX vector. We therefore extend the shortened-support Chien search to a multivector accumulation scheme: the 90 support points are partitioned across two HVX vector accumulators, each holding 64 halfword lanes (with 38 padding lanes in the second). For each locator coefficient σj , the scalar-by-vector multiplication is performed independently on each accumulator and combined via lane-wise XOR; the final scan over the first 90 lanes returns the located-error mask. The same packedvector accumulation strategy extends to two parallel accumulators for HQC-256. The same multi-vector accumulation idea is also used when packed evaluations exceed one HVX vector. Finally, all finite-field lookup tables, alpha-power tables, shortened-support vectors, and generatorpolynomial coefficients are precomputed at compile time (alpha tables, generator polynomials) or initialized once at first use (transposed power tables for the HVX paths). This allows the same decoding kernels to operate across HQC-128, HQC-192, and HQC-256 without modifying the underlying vectorized arithmetic routines. Security scope. This work targets the performance and energy efficiency of HQC decoding on NPUintegrated Qualcomm platforms, and the evaluated backend is not constant-time. Two sources of secretdependent behavior are present. First, following the table-driven Reed–Solomon optimization of OptHQC [10], our finite-field arithmetic (Section 3.3.1) replaces multiplications with logarithm/antilogarithm lookups, which use operand-dependent table indices. Second, the error-locator computation (Algorithm 6) is a branchy Berlekamp–Massey recurrence whose control flow and inner-loop bounds depend on the 10
discrepancy values and the evolving locator degree. The HVX kernels for the Reed–Muller transform, peak selection, syndrome evaluation, and Chien search use fixed loop bounds and data-independent access patterns, but they operate on values derived from the (secret-dependent) received word. We therefore make no claim of resistance to address-dependent microarchitectural leakage or power/timing side channels. A fully constant-time backend—using fixed-flow finite-field arithmetic and a masked, branch-free error-locator computation—is left for future work.
4
Experimental Evaluation
This section evaluates the performance and energy efficiency of the proposed NPU-supported HQC decoder. We first report simulator measurements for all three HQC parameter sets in terms of Hexagon processor cycles, and then provide a substage-level breakdown for HQC-128 to identify the main sources of improvement in the Reed-Muller and Reed-Solomon decoding components. Finally, we present real-device measurements on a Snapdragon 8 Gen 2 development platform for all three HQC parameter sets, reporting latency, energy per decode, throughput per watt, and host CPU utilization. Our proof-of-concept implementation is available at github.com/Hiiamming/pqc-hqc-npu. Across all simulator and real-device runs reported below, the optimized decoder produced output identical to the reference scalar decoder on the full 256-fixture corpus for every parameter set, confirming the bit-level equivalence targeted in Section 3. All fixture corpora used for decoding are generated randomly at each iteration. We refer readers to our proof-of-concept implementation for further details.
4.1
Experiment Settings
4.1.1
Environment
We benchmark the implementation in two execution environments: the cycle-accurate hexagon-sim shipped with the Qualcomm Hexagon SDK, and the on-device cDSP path accessed from an Android host through FastRPC. The simulator binary is executed through the H2 minimal hypervisor and its booter entrypoint. The cDSP image is compiled with the same hexagon-clang configuration as the simulator binary, while the Android host benchmark is cross-compiled with the NDK Bionic toolchain. Throughout the evaluation, we use NPU-supported to denote the cDSP/Hexagon/HVX backend, in contrast to the scalar CPU or scalar Hexagon baselines. 4.1.2
FastRPC communication with the NPU
In the execution context, the CPU requires a communication protocol to offload specific tasks to the NPU. Since the CPU and NPU operate in different execution domains, the CPU cannot directly invoke NPU kernels as ordinary local functions. Instead, it relies on a runtime communication mechanism, namely FastRPC [25], to transfer control information, pass buffer descriptors, and synchronize task execution. In this workflow, the CPU first prepares the input data in a shared I/O buffer that is accessible by both the CPU and the NPU. Rather than copying large data through the control path, the CPU passes only lightweight metadata, such as buffer handles, data sizes, and task parameters. The FastRPC stub on the CPU side marshals these arguments and forwards the request to the NPU-side runtime. The NPU runtime then dispatches the corresponding kernel, reads the input from the shared buffer, performs the computation, and writes the result back to the output buffer. Finally, the completion status is returned to the CPU, which synchronizes and reads the output. The complete workflow is visualized in Figure 4. Unfortunately, each initialization incurs a non-negligible overhead, averaging around 557 µs, which makes per-decode initialization undesirable. To address this issue, we batch multiple decoding instances and offload them to the NPU in a single communication round, thereby amortizing the extra cost. This strategy is natural in practical applications, where devices often process continuously arriving data, especially in streaming video workloads. The detailed measurement is given in Table 8. 4.1.3
Measurement metrics
We report four complementary metrics to evaluate the proposed implementation: simulated processor cycles, real-device latency, device energy, and CPU utilization.
11
CPU Application
write input
Shared I/O Buffer DMA-accessible, zero-copy
buffer handle / descriptor
invoke with buffer
FastRPC Stub User-space proxy, marshals args
NPU subsystem
FastRPC Driver
NPU Runtime
Kernel Execution
Kernel driver, IPC
Schedules compute tasks
Runs NN / signal kernels
completion / status
Figure 4: FastRPC-based NPU task execution flow. Hexagon Pcycles. To avoid simulator startup and teardown effects, we use a paired measurement strategy. We measure both a one-iteration and a three-iteration run, subtract the former from the latter, and normalize by the number of additional decodes: Pcycles/decode =
PcyclesT =3 − PcyclesT =1 . (3 − 1) × Nfix
where Nfix = 256 is the corpus size. The same estimator is used for both the scalar baseline and the NPU-supported variant, as well as for the substage breakdown. Real-device latency and energy. On the Android device, we measure wall-clock latency around the decoding loop and divide by the total number of decodes. Energy is measured by sampling device power-supply voltage and current during execution, integrating power over time, and normalizing by the number of decodes. We disable qprof during energy measurement to avoid perturbing power and clock behavior. CPU utilization. We measure the CPU cost paid by the Android host process under each backend. In the CPU-scalar configuration, this is the process that runs the scalar decoder directly on the Kryo CPU. In the NPU-supported configuration, it is the same host-side benchmark process acting as a FastRPC dispatcher: it submits batched decode work to the cDSP and waits for completion. The measurement wrapper samples /proc/<pid>/task/*/stat while the process is alive, sums the user and system jiffies across all of the process threads, and converts the tick delta using getconf CLK_TCK. We then normalize the resulting host CPU time in two ways. The process CPU percentage divides host CPU time by the wall-clock interval, so 100% corresponds to one fully loaded CPU core on the Snapdragon 8 Gen 2 platform rather than to the entire multi-core SoC. The CPU ms/decode metric divides the same host CPU time by the number of completed decodes. Finally, CPU reduction compares CPU ms/decode against the CPU-scalar baseline and therefore quantifies host-side offload only; NPU-supported decoding still consumes Hexagon cycles on the cDSP, which are reflected separately in the latency and energy measurements.
12
4.2
Simulation Results
The simulator benchmark is conducted on the current 256-fixture decoding corpus for each HQC parameter set and reports Hexagon processor cycles (Pcycles). Instead of reporting raw hexagon-sim totals as the main result, we use the paired T = 1 and T = 3 runs to expose the actual normalized cost. The ∆ columns in Table 3 are the difference between the three-iteration and one-iteration runs; the estimated cycles per decode are then obtained by dividing ∆Pcycles by ∆decodes. This presentation keeps the fixed simulator/setup overhead separate from the per-decode estimate. Parameter HQC-128 HQC-128 HQC-192 HQC-192 HQC-256 HQC-256
Backend Scalar NPU-supported Scalar NPU-supported Scalar NPU-supported
∆Pcycles 488,326,812 21,233,214 678,800,028 25,714,332 1,405,108,650 41,295,582
∆decodes 512 512 512 512 512 512
Estimated Pcycles/decode 953,763 41,471 1,325,781 50,223 2,744,353 80,655
Speedup 1.00x 23.00x 1.00x 26.40x 1.00x 34.03x
Table 3: Paired Hexagon simulator measurements for full HQC decoding. The reported per-decode cost is ∆Pcycles/∆decodes from the T = 1 and T = 3 runs, not a raw total-cycle division. Relative to the scalar baseline, the NPU-supported path is 23.00×, 26.40×, and 34.03× faster for HQC-128, HQC-192, and HQC-256, respectively.
4.3
Substage Analysis
The substage benchmark compares the scalar baseline with the NPU-supported path. Reed-Muller substage costs are first estimated from paired one- and three-iteration measurements per RM block, then multiplied by the 46 Reed-Muller blocks used in one HQC-128 decode. Reed-Solomon substage costs use the same paired estimate directly per decode. The table reports the main optimized substages rather than an exhaustive decomposition of the full decoder. Substage Reed-Muller Hadamard Reed-Muller find peak Reed-Solomon syndrome Reed-Solomon error-locator polynomial Full decode estimate
Scalar 263,175 71,217 162,312 119,595 953,763
NPU-supported 17,950 6,081 3,517 6,581 41,471
Table 4: Paired Pcycle breakdown of selected optimized HQC-128 decoding substages. Reed-Muller rows are converted from per-block cost to per-decode cost by multiplying by 46 blocks. Note that this table does not include repetition aggregation, codeword loading, and other small substages.
4.4
Real-Device Results
The real-device experiments were conducted on a Snapdragon® 8 Gen 2 Mobile Hardware Development Kit, model HDK8550, based on the Qualcomm Snapdragon SM8550P application processor. According to the manufacturer specification, this platform includes an 8-core 64-bit Kryo CPU, consisting of one Arm Cortex-X3 prime core up to 3.2 GHz, four performance cores up to 2.8 GHz, and three efficiency cores up to 2.0 GHz. It also includes a Qualcomm Hexagon processor equipped with Hexagon Vector eXtensions (HVX), scalar and tensor accelerators, micro tile inferencing, Hexagon Direct Link, and support for INT4, INT8, INT16, and FP16 arithmetic. Note that the simulator speedup is measured against a Hexagon scalar baseline, whereas the real-device speedup is against the ARM Cortex CPU scalar baseline; the two are not directly comparable. The real-device measurements use the corresponding 256-fixture decoding corpus for each HQC parameter set. Unlike the simulator benchmark, which reports Hexagon Pcycles, the real-device benchmark reports host-observed latency and direct device energy. Each reported value is the mean of five runs, and 13
Reed–Muller Hadamard
Reed–Muller find peak
Reed–Solomon syndrome
Reed–Solomon ELP
0
0.5
1
1.5
2
2.5
3
Pcycles/decode (×10 ) 5
Scalar
NPU-supported
Figure 5: Comparison of selected optimized decoding substages between the scalar baseline and the NPUsupported backend (ELP is abbreviated for error locator polynomial). Lower is better. each run performs 32,000 decodes. The NPU-supported backend uses the current non-worker FastRPC path, where one batched remote call executes the full decode loop on the cDSP. Energy is measured from Android power-supply voltage/current samples with qprof disabled. Here, qprof refers to Qualcomm’s profiler for DSP/NPU utilization and clock-state diagnostics; its measurements are used only as diagnostic evidence and are not used for the energy claims. The speedup, decodes/s/W, and energy-gain columns are computed per run and then averaged over the five runs. Therefore, the reported speedup and energy-gain values are means of per-run ratios, not ratios recomputed from the rounded mean latency or mean energy columns. In particular, the energy-gain column can differ from E CPU /E NPU because direct-energy measurements have higher run-to-run variability.
HQC HQC-128 HQC-128 HQC-192 HQC-192 HQC-256 HQC-256
Backend CPU scalar NPU-supported CPU scalar NPU-supported CPU scalar NPU-supported
us/decode 81.144 39.173 103.531 56.065 228.082 116.333
uJ/decode 189.108 10.593 246.480 23.645 584.573 36.078
decodes/s/W 5,641.362 110,083.297 4,258.922 53,040.740 1,747.860 30,497.824
Speedup 1.00x 2.07x 1.00x 1.85x 1.00x 1.96x
Energy gain 1.0x 18.13x 1.0x 11.77x 1.0x 16.81x
Table 5: Real-device latency, energy, and throughput-per-watt measurements across HQC parameter sets. Values are means over five runs; run-to-run variability is summarized separately in Table 6. The decodes/s/W column is the per-run throughput (decodes/s, from the reported per-decode latency) divided by the net active power (run minus idle power); like the energy-gain column, it is computed per run and then averaged over the five runs. Across all three HQC parameter sets, the NPU-supported backend improves both latency and energy efficiency over the scalar CPU baseline. The measured speedup is 1.85× to 2.07×, and the energy gain is 11.77× to 18.13×. On the current device run, NPU-supported latency increases with the HQC parameter set size, while still reducing both wall-clock time and energy per decode relative to the CPU baseline.
14
HQC HQC-128 HQC-128 HQC-192 HQC-192 HQC-256 HQC-256
Backend CPU scalar NPU-supported CPU scalar NPU-supported CPU scalar NPU-supported
us/decode CV 0.17% 0.05% 0.08% 0.21% 0.10% 0.07%
uJ/decode CV 3.72% 14.84% 4.59% 34.40% 3.33% 18.66%
CPU ms/decode CV 0.83% 59.27% 0.85% 81.44% 0.32% 22.83%
Table 6: Run-to-run variability for the direct real-device measurements, reported as coefficient of variation CV = σ/µ. Latency is stable across runs; energy has higher variability because it is derived from boardlevel power samples.
584.57
800
36.08
23.65
10.59
200
246.48
400 189.11
uJ/decode
600
0 HQC-128
HQC-192 CPU scalar
HQC-256
NPU-supported
Figure 6: Real-device energy per decode. Lower is better. In addition to latency and energy, Table 7 reports the CPU time consumed by the benchmark host process itself. These numbers are collected by wrapping the benchmark with measure_process_cpu.sh. The script samples the process and thread accounting files under /proc/<pid>/task/*/stat while the benchmark is running, sums user and system CPU ticks, and converts them to milliseconds using the Linux clock tick rate. The same wrapper is used for both backends: for CPU scalar, the measured process runs the scalar decoder directly; for NPU-supported, the measured process mostly submits FastRPC work to the cDSP and waits for completion. The process CPU % column is the sampled host CPU time divided by the wall-clock runtime of the benchmark. It is normalized to one CPU core: 100% means the process kept one CPU core fully busy on average, not the whole multi-core SoC. The CPU ms/decode column is the same host CPU time divided by the number of completed decodes. The CPU reduction column is computed from CPU ms/decode as CPU ms/decodeNPU 100 × 1 − . CPU ms/decodescalar The reported CPU-reduction values are computed with this formula for each paired run and then averaged. They should therefore be interpreted as the mean per-run host-side CPU offload, not as a value recomputed from the rounded mean CPU ms/decode columns in the table This metric measures host-side CPU offload only; the NPU-supported decoder still consumes Hexagon cycles on the cDSP. The process-level CPU measurements show why CPU offloading matters beyond energy alone. When the CPU consumes nearly all of one core decoding HQC, the host has less room for other application or system work. Moving the decoding workload to the NPU reduces host CPU ms/decode by 99.1%–99.7% 15
HQC HQC-128 HQC-128 HQC-192 HQC-192 HQC-256 HQC-256
Backend CPU scalar NPU-supported CPU scalar NPU-supported CPU scalar NPU-supported
process CPU % 93.606 1.498 94.538 0.678 97.243 0.606
CPU ms/decode 0.0803125 0.0006875 0.1025625 0.0004375 0.2268750 0.0007500
CPU reduction 0.000% 99.145% 0.000% 99.575% 0.000% 99.669%
Table 7: Process-level CPU utilization and CPU-time reduction on the real device. across all HQC parameter sets. This reduction is a host-side offload metric only; the NPU-supported decode still consumes Hexagon cycles, which are reflected in the latency and energy measurements above. We also isolate the FastRPC boundary cost. The batched row uses the same non-worker batched decode benchmark as the real-device latency table, while the “decode-one” experiment makes one FastRPC call per decode. Table 8 reports only the boundary-sensitive modes: a no-op ping, one-decode-per-RPC, and the batched path used to quantify boundary amortization. HQC HQC-128 HQC-192 HQC-256
Ping us/RPC 552.804 530.990 535.708
Decode-one us/decode 590.640 604.201 629.596
Batched us/decode 39.205 56.234 116.104
Decode-one slowdown 15.07x 10.74x 5.42x
Table 8: FastRPC boundary overhead on the real device. Values are means over five runs; variability is summarized separately in Table 9. HQC HQC-128 HQC-192 HQC-256
Ping CV 1.47% 2.71% 2.73%
Decode-one CV 1.93% 1.03% 2.10%
Batched CV 0.08% 0.68% 0.11%
Table 9: Run-to-run variability for the FastRPC boundary measurements, reported as coefficient of variation CV = σ/µ. The FastRPC no-op boundary alone is about 531–553 µs per call, which is much larger than the batched per-decode cost for all three HQC parameter sets. Calling FastRPC once per decapsulation is therefore 5.42× to 15.07× slower than batching the decode loop inside one remote call. Representative cached payload movement remains secondary to the boundary itself: the measured cached input overhead is on the order of 575–594 µs per RPC for the current build. Thus, the real-device NPU numbers should be interpreted as batched cDSP throughput with heavily amortized FastRPC overhead, not as the latency of an API that performs one remote call per decapsulation.
5
Conclusion
This paper presented an optimized implementation of HQC decoding on Qualcomm Hexagon processors in NPU-integrated devices. We showed that HQC decoding is well matched to the Hexagon/HVX vector execution model, since its dominant Reed-Muller and Reed-Solomon components naturally operate on vector-structured data such as reliability vectors, Hadamard-transform coefficients, syndrome vectors, finite-field elements, and packed support points. Based on this observation, we redesigned the main decoding kernels around HVX-friendly data layouts and execution patterns, including a vectorized ReedMuller Hadamard transform, scalar-equivalent peak selection, HVX-oriented finite-field multiplication vectorized syndrome computation, and shortened-support Chien search. Our evaluation demonstrates that the proposed Hexagon/HVX-assisted implementation substantially reduces the cost of HQC decoding. In Hexagon simulator measurements for HQC-128, the optimized implementation reduces the full decoding cost from 953,763 to 41,471 Pcycles per decode, corresponding to a 23.00× speedup and a 95.7% reduction in Pcycles; the same approach yields 26.40× and 34.03× 16
speedups for HQC-192 and HQC-256, respectively. On the real device, where the NPU path additionally pays the FastRPC boundary cost, the batched backend improves end-to-end latency over the ARM CPU scalar baseline by 2.07×, 1.85×, and 1.96×, and improves direct-energy efficiency by 18.13×, 11.77×, and 16.81× for HQC-128, HQC-192, and HQC-256, respectively. At the same time, it reduces host-side CPU time per decode by 99.1%–99.7%, freeing the application processor for other work while the decode runs on the cDSP. Because a single FastRPC boundary crossing (531–553 µs) dominates one isolated decode, and one-decode-per-call execution costs about 591–630 µs per decode, these real-device gains are obtained by batching the decode loop into one remote call; the reported numbers should therefore be read as batched cDSP throughput with amortized FastRPC overhead rather than as the latency of a one-decode-per-call interface. These results indicate that NPU-integrated mobile platforms can provide an effective execution backend not only for AI-oriented workloads, but also for structured post-quantum cryptographic decoding when the underlying kernels are reformulated around the available vector execution model. Our optimizations target the concatenated decoding stage of HQC; combining them with an accelerated sparse polynomial product for the full decapsulation path is a natural next step on the same backend. As future work, we plan to investigate fully constant-time finite-field arithmetic for all scalar and vector operations, strengthen the side-channel resilience of the backend, integrate a worker-pool cDSP schedule to further amortize host coordination, and extend the same hardware-aware optimization methodology to other code-based and post-quantum cryptographic primitives. Declaration of Generative AI and AI-assisted technologies in the writing process. During the preparation of this work, the authors used AI-assisted tools to assist with language editing, manuscript polishing, and code drafting/debugging for the experimental implementation. After using these tools, the authors reviewed, edited, and verified the manuscript content, implementation, and experimental results as necessary, and take full responsibility for the content of the publication.
17
References [1] Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332, 1999. [2] National Institute of Standards and Technology. Module-lattice-based digital signature standard. Federal Information Processing Standards Publication 204, National Institute of Standards and Technology, 2024. [3] National Institute of Standards and Technology. Module-lattice-based key-encapsulation mechanism standard. Federal Information Processing Standards Publication 203, National Institute of Standards and Technology, 2024. [4] National Institute of Standards and Technology. Stateless hash-based digital signature standard. Federal Information Processing Standards Publication 205, National Institute of Standards and Technology, 2024. [5] National Institute of Standards and Technology. Status report on the fourth round of the NIST postquantum cryptography standardization process. NIST Interagency/Internal Report 8545, National Institute of Standards and Technology, 2025. [6] HQC Team. Hamming Quasi-Cyclic (HQC). https://pqc-hqc.org/doc/hqc_specifications_ 2025_08_22.pdf, August 2025. Specification document, version 2025-08-22. [7] National Institute of Standards and Technology. Nine candidates advance to the third round of the additional digital signatures for the PQC standardization process. https://csrc.nist.gov/News/ 2026/nist-advances-9-candidates-to-the-3rd-round-of-pqc, 2026. Accessed 2026-05-28. [8] Ward Beullens. MAYO: Practical post-quantum signatures from oil-and-vinegar maps, 2021. [9] Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, and Benjamin Wesolowski. SQISign: Compact post-quantum signatures from quaternions and isogenies. In Advances in Cryptology – ASIACRYPT 2020, volume 12491 of Lecture Notes in Computer Science, pages 64–93. Springer, 2020. [10] Ben Dong, Hui Feng, and Qian Wang. OptHQC: Optimize HQC for high-performance post-quantum cryptography, 2025. [11] DongCheon Kim, JunHyeok Choi, SeungYong Yoon, and Seog Chung Seo. Optimized implementation of HQC on Cortex-M4. ICT Express, 11:939–944, 2025. [12] Sanjay Deshpande, Chuanqi Xu, Mamuri Nawan, Kashif Nawaz, and Jakub Szefer. Fast and efficient hardware implementation of HQC. In Selected Areas in Cryptography – SAC 2023, volume 14201 of Lecture Notes in Computer Science, pages 297–321. Springer, 2023. [13] Yiran Chen, Yuan Xie, Linghao Song, Fan Chen, and Tianqi Tang. A survey of accelerator architectures for deep neural networks. Engineering, 6(3):264–274, 2020. [14] Qualcomm Technologies, Inc. Qualcomm hexagon NPU. https://www.qualcomm.com/processors/ hexagon, 2026. Accessed 2026-05-28. [15] Qualcomm Technologies, Inc. Qualcomm Hexagon V79 HVX Programmer Reference Manual, 2025. 80-N2040-61, January 16, 2025. [16] Ridwane Aissaoui, Jean-Christophe Deneuville, Christophe Guerber, and Alain Pirovano. A performant quantum-resistant KEM for constrained hardware: Optimized HQC. In Proceedings of the 21st International Conference on Security and Cryptography (SECRYPT 2024), pages 668–673. SCITEPRESS, 2024. [17] Francesco Antognazza, Alessandro Barenghi, and Gerardo Pelosi. An efficient and unified RTL accelerator design for HQC-128, HQC-192, and HQC-256. IEEE Transactions on Computers, 74(7):2306– 2320, 2025.
18
[18] Yazheng Tu, Pengzhou He, Çetin Kaya Koç, and Jiafeng Xie. LEAP: Lightweight and efficient accelerator for sparse polynomial multiplication of HQC. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 31(6):892–896, 2023. [19] Antonio Ras, Antoine Loiseau, Mikaël Carmona, Simon Pontié, Guénaël Renault, Benjamin Smith, and Emanuele Valea. Optimizing HQC using frobenius additive FFT on a RISC-V-based system-onchip. In Proceedings of the 2025 28th Euromicro Conference on Digital System Design (DSD 2025), pages 608–615. IEEE, 2025. [20] Amin Abdulrahman, Vincent Hwang, Matthias J. Kannwischer, and Amber Sprenkels. Faster Kyber and Dilithium on the Cortex-M4, 2022. Published at ACNS 2022. [21] Xavier Carril, Charalampos Kardaris, Jordi Ribes-González, Oriol Farràs, Carles Hernández, Vatistas Kostalabros, Joel Ulises González-Jiménez, and Miquel Moretó. Hardware acceleration for highvolume operations of CRYSTALS-Kyber and CRYSTALS-Dilithium. ACM Transactions on Reconfigurable Technology and Systems, 17(3), 2024. [22] Emma Urquhart and Frank Stajano. Acceleration of core post-quantum cryptography primitive on open-source silicon platform through hardware/software co-design. In Cryptology and Network Security – CANS 2024, volume 14905 of Lecture Notes in Computer Science, pages 144–161. Springer, 2024. [23] Robert T. Chien. Cyclic decoding procedures for Bose-Chaudhuri-Hocquenghem codes. IEEE Transactions on Information Theory, 10(4):357–363, 1964. [24] Elwyn R. Berlekamp. Algebraic Coding Theory. McGraw-Hill, 1968. [25] Qualcomm Technologies, Inc. Hexagon DSP User Guide. Qualcomm Technologies, Inc., 2018. Document 80-VB419-108.
19
Appendix A
Supplementary Implementation Details
This section provides supplementary implementation details for the optimized HQC decoder. We first present the pseudocode of the main HVX-assisted routines used in the Reed-Muller and Reed-Solomon decoding stages. We then summarize the mapping between the abstract vector operations used throughout the paper and representative Qualcomm Hexagon HVX intrinsics.
A.1
Pseudocode
Algorithm 1 HVX-based Hadamard transform for Reed-Muller decoding. Input: Source buffer src ∈ Z128 and temporary buffer dst ∈ Z128 of signed 16-bit values. Output: Hadamard-transformed vector stored in the buffer pointed to by p1 . 1: p1 ← src, p2 ← dst 2: for pass = 0 to 6 do 3: lo ← p1 [0 : 63], hi ← p1 [64 : 127] 4: (dlo , dhi ) ← VDEAL2(hi, lo, 2) ▷ two-vector deinterleaving 5: ve ← VDEALH(dlo ) ▷ pack even lanes 6: vo ← VDEALH(dhi ) ▷ pack odd lanes 7: sum ← VADDH(ve , vo ) ▷ sum half 8: diff ← VSUBH(ve , vo ) ▷ difference half 9: p2 [0 : 63] ← sum, p2 [64 : 127] ← diff 10: swap(p1 , p2 ) ▷ next pass consumes the output 11: end for 12: return p1
Algorithm 2 HVX-based peak detection. Input: Hadamard-transformed buffer transform ∈ Z128 of signed 16-bit values. Output: Encoded peak position for Reed–Muller decoding. 1: row0 ← transform[0 : 63], row1 ← transform[64 : 127] ▷ load two HVX vectors 2: abs0 ← VABS(row0 ), abs1 ← VABS(row1 ) ▷ lane-wise magnitudes 3: max ← VMAX(abs0 , abs1 ) ▷ pairwise maximum 4: for s ∈ {64, 32, 16, 8, 4, 2} do 5: max ← VMAX(max, VROTs (max)) ▷ rotation-based max reduction 6: end for 7: a⋆ ← max[0] ▷ global maximum magnitude 8: target ← VSPLAT(a⋆ ) 9: sentinel ← VSPLAT(0x7f f f ) ▷ invalid large index 10: idx0 ← rm_index_lo, idx1 ← rm_index_hi 11: mask0 ← VCMPEQ(abs0 , target) 12: mask1 ← VCMPEQ(abs1 , target) ▷ mark tied maxima 13: pos0 ← VSELECT(mask0 , idx0 , sentinel) 14: pos1 ← VSELECT(mask1 , idx1 , sentinel) ▷ keep only valid peak indices 15: peak ← VMIN(pos0 , pos1 ) 16: for s ∈ {64, 32, 16, 8, 4, 2} do 17: peak ← VMIN(peak, VROTs (peak)) ▷ minimum-index tie break 18: end for 19: i⋆ ← peak[0] 20: v ⋆ ← transform[i⋆ ] 21: if v ⋆ > 0 then 22: i⋆ ← i⋆ | 128 ▷ encode sign bit 23: end if 24: return i⋆
20
Algorithm 3 (XTIME_VEC) Vectorized multiplication by x over F28 Require: Vector x whose lanes contain elements of F28 Ensure: Vector y where yi = X · xi mod P (X), where P (X) = X 8 + X 4 + X 3 + X 2 + 1. 1: carry ← VAND(VSHR7 (x), VSPLAT(1)) ▷ MSB of each lane 2: mask ← VSUB(VZERO(), carry) ▷ expand carry bits to masks 3: shifted ← VSHL1 (x) ▷ multiply by X 4: red ← VAND(mask, VSPLAT(0x1d)) ▷ select reduction term 5: y ← VXOR(shifted, red) ▷ reduce modulo P (X) 6: y ← VAND(y, VSPLAT(0xf f )) ▷ keep 8 bits 7: return y
Algorithm 4 (SCALAR_VEC) Vectorized scalar-by-vector multiplication over F28 Require: Scalar field element a ∈ F28 Require: Vector b = (b0 , . . . , b63 ) of field elements Ensure: Vector (ab0 , . . . , ab63 ) 1: acc ← VZERO() ▷ product accumulator 2: a ← VSPLAT(a) ▷ broadcast scalar 3: one ← VSPLAT(1) 4: zero ← VZERO() 5: for t ← 7 downto 0 do 6: bt ← VAND(VSHRt (b), one) ▷ extract bit t 7: mask ← VSUB(zero, bt ) ▷ bit-to-mask 8: acc ← XTIME_VEC(acc) ▷ shift partial product 9: acc ← VXOR acc, VAND(a, mask) ▷ conditional add 10: end for 11: return acc
Algorithm 5 HVX-based vectorized syndrome computation. Input: Received word c = (c0 , . . . , cn1 −1 ) ∈ Fn281 . (n −1)×64 Precomputed: Power table A ∈ F28 1 with A[j − 1] = αj , α2j , . . . , α(2δ)j , 0, . . . , 0 ,
1 ≤ j < n1 .
Equivalently, A[j − 1][i] = alpha_ij_pow[i][j] for 0 ≤ i < 2δ and 0 otherwise. The table is built once and reused across all decode invocations. Ln1 −1 Output: Syndrome vector (Se0 , . . . , Se2δ−1 ) with Sei = c0 ⊕ j=1 cj α(i+1)j . 1: acc ← VZERO() ▷ accumulator over all 2δ syndrome lanes 2: for j = 1 to n1 − 1 do 3: aj ← A[j − 1] ▷ aligned 64-lane load 4: p ← SCALAR_VEC(cj , aj ) ▷ Algorithm 4 5: acc ← VXOR(acc, p) 6: end for 7: acc ← VXOR(acc, VSPLAT(c0 )) ▷ inject the constant term e e 8: Copy lanes (acc[0], . . . , acc[2δ − 1]) to (S0 , . . . , S2δ−1 ) e0 , . . . , Se2δ−1 ) 9: return (S
21
Algorithm 6 Branchy Berlekamp–Massey error-locator computation (fastest backend). Require: Syndrome vector S = (S0 , . . . , S2δ−1 ) Ensure: Error-locator polynomial σ = (σ0 , . . . , σδ ) and its degree deg σ 1: σ ← (1, 0, . . . , 0); b ← (1, 0, . . . , 0) ▷ locator and auxiliary polynomial 2: deg σ ← 0; deg b ← 0; m ← 1; dρ ← 1 3: for µ = 0 to 2δ − 1 do 4: d ← Sµ 5: for i = 1 to deg σ do 6: d ← d ⊕ GFmul(σi , Sµ−i ) ▷ discrepancy (table-driven GF) 7: end for 8: if d ̸= 0 then 9: γ ← GFmul d, GFinv(dρ ) 10: t←σ ▷ save current locator 11: u ← min(m + deg b, δ) 12: for i = m to u do 13: σi ← σi ⊕ GFmul(γ, bi−m ) ▷ locator update 14: end for 15: if 2 deg σ ≤ µ then ▷ length change 16: deg′ ← µ + 1 − deg σ 17: b ← t; deg b ← deg σ 18: deg σ ← deg′ ; m ← 1; dρ ← d 19: else 20: m←m+1 21: end if 22: else 23: m←m+1 24: end if 25: end for 26: return (σ[0..δ], deg σ)
22
A.2
Abstraction mapping table Abstraction
HVX intrinsic realization
Technical meaning
VADD
Q6_Vh_vadd_VhVh
Add two vectors lane by lane.
VSUB
Q6_Vh_vsub_VhVh
Subtract two vectors lane by lane.
VABS
Q6_Vh_vabs_Vh
Take the absolute value of each signed halfword lane.
VMAX
Q6_Vh_vmax_VhVh
Compute the lane-wise maximum of two vectors.
VMIN
Q6_Vh_vmin_VhVh
Compute the lane-wise minimum of two vectors.
VSPLAT
Q6_Vh_vsplat_R
Broadcast one scalar value to all vector lanes.
VXOR
Q6_V_vxor_VV
Compute bitwise XOR between two vectors.
VAND
Q6_V_vand_VV
Compute bitwise AND between two vectors.
VSHLs
Q6_Vh_vasl_VhR
Shift each lane left by s bits.
VSHRs
Q6_Vuh_vlsr_VuhR
Shift each unsigned lane right by s bits.
VROTs
Q6_V_vror_VR
Rotate the whole vector register by s bytes.
VDEAL2
Q6_W_vdeal_VVR
Deinterleave two input vectors into two reordered output vectors.
VDEALH
Q6_Vh_vdeal_Vh
Deinterleave halfword lanes inside one vector.
VCMPEQ
Q6_Q_vcmp_eq_VhVh
Compare two vectors lane by lane and produce a predicate mask.
VSELECT
Q6_V_vmux_QVV
Select lanes from two vectors according to a predicate mask.
Q6_Vh_vmax_VhVh
Reduce all lanes to one maximum value using rotations and lane-wise maxima.
VREDUCE_MAX
with Q6_V_vror_VR VREDUCE_MIN
Q6_Vh_vmin_VhVh with Q6_V_vror_VR
VZERO
Reduce all lanes to one minimum value using rotations and lane-wise minima. Generate the zero vector
Q6_V_Zero
Table 10: Mapping between the NPU abstraction and representative Qualcomm Hexagon HVX intrinsics.
23