Hardware Realization and Implementation Security Evaluation of HQC, A NIST PQC Standard

The rise of large-scale quantum computers threatens to break the public-key cryptosystems, like RSA, that secure our digital infrastructure. Post-Quantum Cryptography (PQC) offers a solution by providing algorithms that run on classical computers but are believed to be secure against both classical and quantum attacks. Global standardization bodies, most notably NIST, have been evaluating PQC candidates for nearly a decade based on security, cost (e.g., key sizes), and implementation efficiency. This talk focuses on the hardware implementation and security of the Hamming Quasi-Cyclic (HQC) algorithm, a code-based Key Encapsulation Mechanism (KEM) selected by NIST.

HQC: A Code-Based Key Encapsulation Mechanism

HQC is a Key Encapsulation Mechanism (KEM) whose security is based on the hardness of the syndrome decoding problem. It is constructed using concatenated error-correcting codes, specifically shortened Reed-Solomon and duplicated Reed-Muller codes.

The core operation repeated throughout its primitives (key generation, encapsulation, and decapsulation) is the polynomial calculation s = x + h * y. In this setup, h and s are public, while x and y are secret, sparse polynomials with a fixed weight (number of non-zero elements). Finding the secret x and y given the public values is computationally hard.

Hardware Implementation: Overcoming Bottlenecks

Hardware implementations on platforms like FPGAs and ASICs are essential for improving the performance, security, and energy efficiency of PQC algorithms. The design process involves identifying and mitigating bottlenecks.

Performance Bottleneck: Polynomial Multiplication

Profiling HQC reveals that polynomial multiplication is the primary performance bottleneck, consuming 70-80% of the clock cycles across all primitives.

• Standard Techniques: Methods like Schoolbook (O(n²)), Karatsuba (O(n¹⋅⁵⁸⁵)), and Toom-Cook offer improvements, but a more specialized approach is possible.
• Proposed Solution: Sparse Multiplication: Since one of the polynomial inputs (y or x) is always a sparse vector with a fixed, small weight (w), this property can be leveraged. Instead of performing a full multiplication, the non-sparse polynomial is shifted according to the indices of the non-zero elements in the sparse polynomial, and the results are accumulated. This reduces the complexity to O(n * w), which is significantly faster.
• Hardware Realization: This is implemented using a variable shifter. To manage resources, an interleaved reduction technique is used, which performs the reduction back into the field x^n - 1 during the multiplication process. This avoids the need to store a large 2n-sized intermediate polynomial, saving both area and memory.
• Comparison to NTT/FFT: While popular in lattice-based schemes, Number Theoretic Transform (NTT) or FFT-style multiplication is not directly applicable to HQC’s binary field. Workarounds like Frobenius Additive FFTs exist but introduce significant overhead from basis conversions, making them less efficient than the proposed sparse multiplication method.

Security Vulnerability: Side-Channel Attacks

The handling of secret keys presents a target for side-channel attacks. A notable vulnerability was found in the fixed-weight vector generation process.

• The Vulnerability: The original HQC specification used a rejection sampling method to generate the sparse secret vectors. This process had a non-constant time behavior, which was exploited in a timing attack to recover parts of the secret key from the decapsulation process.
• Countermeasure 1: Fast and Non-Biased Method: A proposed hardware-friendly fix involves pre-drawing more random bits than necessary and storing them in a buffer (e.g., a block RAM). The algorithm then iterates through the entire buffer to build the vector, masking the true number of cycles required. This makes the process constant-time, though there is a small, parameterizable probability of failure if the buffer is exhausted.
• Countermeasure 2: Constant Weight Word Method: An algorithmic fix, later recommended by the HQC team, avoids rejection sampling entirely. It uses a different method to handle threshold and duplicate checks, which introduces a small, cryptographically insignificant bias. Both methods were implemented and compared, with the first being faster but the second offering a stronger guarantee at the algorithmic level.

Results and Future Work

The proposed hardware designs, with both balanced and high-speed variants, demonstrate a significant speedup for key generation, encapsulation, and decapsulation compared to highly optimized software implementations using AVX instructions.

Future work is focused on exploring more advanced side-channel threats. An ongoing project investigates power side-channel attacks, specifically Correlation Power Analysis (CPA), on the variable shifter used in the polynomial multiplier. The goal is to recover the secret key by analyzing power traces related to memory access patterns. Potential countermeasures being explored include masking (effective but expensive) and cheaper alternatives like shuffling or shifting the indices of the secret polynomials for each operation.

• Tags:
• Cryptography
• Post-Quantum Cryptography
• HQC
• PQC
• Hardware Acceleration
• FPGA
• Side-Channel Attacks
• NIST Standardization