Abstract:
This technical presentation details the hardware architecture and optimization of Hamming Quasi-Cyclic (HQC), a code-based Key Encapsulation Mechanism (KEM) currently under the NIST Post-Quantum Cryptography (PQC) standardization process. The analysis identifies polynomial multiplication as the primary computational bottleneck, accounting for 70–80% of total execution cycles. To mitigate this, a sparse multiplication strategy is proposed, leveraging the fixed weight of secret vectors to achieve $O(n \cdot w)$ complexity, significantly outperforming generalized Karatsuba or NTT-based approaches in the binary field $\mathbb{F}_2$. Furthermore, the session addresses critical implementation security vulnerabilities, specifically timing attacks on fixed-weight vector generation and Correlation Power Analysis (CPA) on variable shifters. Proposed countermeasures include constant-weight word methods and architectural shuffling to ensure side-channel resistance on FPGA and ASIC platforms.
Step 4: Bulleted Summary
11:29 – Introduction to HQC Hardware Design: Discussion led by Sanjay Despande (Northwestern University) focusing on the hardware efficiency and security of the HQC scheme within the NIST PQC portfolio.
12:42 – Motivation for PQC Deployment: The necessity of transitioning from RSA/ECC to quantum-resistant primitives is driven by the threat posed by Shor’s algorithm to classical public-key infrastructure.
14:11 – NIST Standardization Context: HQC is a code-based KEM candidate selected for further evaluation due to its security properties and performance characteristics; it relies on the hardness of the syndrome decoding problem.
18:18 – HQC Architectural Fundamentals: The scheme utilizes concatenated codes (shortened Reed-Solomon and duplicated Reed-Muller). The core operation involves polynomial multiplication and addition in $\mathbb{F}_2[x] / (x^n - 1)$.
20:37 – Sparse Polynomial Dynamics: Key security parameters involve high-degree polynomials ($n$) where secret components ($x, y$) are sparse with a fixed weight ($w$). The public value $h$ is pseudo-randomly generated via SHAKE-256.
23:10 – Identification of Performance Bottlenecks: Profiling reveals that polynomial multiplication dominates 70–80% of the clock cycles across key generation, encapsulation, and decapsulation.
23:54 – Mitigation of Timing Attacks: Rejection sampling in the original fixed-weight vector generation was vulnerable to timing leaks. The presenter proposes a constant-time "Constant Weight Word" method to eliminate non-deterministic behavior during vector sampling.
28:33 – Optimization via Sparse Multiplication: Traditional $O(n^2)$ or Karatsuba $O(n^{1.58})$ methods are bypassed in favor of a sparse multiplier ($O(n \cdot w)$). This leverages the known weight of the sparse operand to reduce complexity through selective shifting and XOR accumulation.
31:11 – Hardware Implementation of Variable Shifters: To manage FPGA resources, the design uses a parameterized sequential approach for shifting, balancing area (Look-Up Tables/Registers) against throughput.
33:58 – NTT/FFT Comparison: Traditional Number Theoretic Transform (NTT) and Frobenius additive FFTs are analyzed but found to incur significant area/time overhead for HQC’s specific binary field requirements compared to sparse-optimized architectures.
40:05 – Benchmark Comparisons: Evaluation against High-Level Synthesis (HLS) and hardware/software co-designs shows that hand-optimized Register Transfer Level (RTL) achieves superior Time-Area Products (TAP).
44:38 – Side-Channel Vulnerabilities (Ongoing Research): Identification of a power-based side-channel vulnerability in variable shifters. Correlation Power Analysis (CPA) can potentially leak indices of the sparse secret key by observing memory write offsets.
46:58 – Proposed Countermeasures: Evaluation of masking (high overhead) versus lower-cost alternatives like index shuffling and operand shifting to decorrelate power traces from secret data.
Reviewer Recommendations:
This topic is best reviewed by Hardware Security Researchers, Cryptographic Engineers, and NIST Standardization Evaluators.
Summary for Reviewers:
The provided research demonstrates a high-performance RTL implementation of HQC that prioritizes sparse multiplication to resolve the inherent bottlenecks of code-based cryptography. It successfully addresses known timing leaks in vector generation and identifies a critical new side-channel vector in variable shifters, providing a roadmap for side-channel resistant PQC hardware accelerators.