Efficient Homomorphic Integer Computer from CKKS

Introduction to Post-Quantum Cryptography and HQC

Modern public-key cryptosystems, such as RSA, form the backbone of today’s digital infrastructure but are vulnerable to attacks from large-scale quantum computers running Shor’s algorithm. Post-Quantum Cryptography (PQC) aims to develop new cryptographic algorithms that are secure against both classical and quantum computers but run on classical hardware.

The NIST PQC standardization process, initiated in 2016, has been evaluating candidates for Key Encapsulation Mechanisms (KEMs) and digital signatures. One of the schemes selected for standardization is HQC (Hamming Quasi-Cyclic), a code-based KEM. The evaluation of these candidates rests on three main pillars:

1. Security: Resilience against known attacks.
2. Efficiency: Performance in both hardware and software, along with implementation security.
3. Cost: Factors like key sizes and signature sizes.

This work focuses on the hardware implementation efficiency and security of HQC, which is crucial for improving performance and energy efficiency in real-world deployments on platforms like FPGAs and ASICs.

HQC Scheme Overview

HQC is a Key Encapsulation Mechanism (KEM) whose security is based on the syndrome decoding hard problem. It utilizes concatenated codes, specifically shortened Reed-Solomon and duplicated Reed-Muller codes.

The core operation repeated across all HQC primitives (Key Generation, Encapsulation, Decapsulation) is the polynomial computation: s = x + h * y

Here, h and s are public polynomials, while x and y are secret, sparse polynomials with a fixed number of non-zero elements (a fixed “weight”). The difficulty lies in finding the secret polynomials x and y given the public values.

Identifying and Addressing Implementation Bottlenecks

A thorough analysis of HQC reveals two primary bottlenecks for hardware implementation:

1. Performance Bottleneck: Polynomial multiplication is the most computationally intensive part, accounting for 70-80% of the clock cycles across different security levels.
2. Security Bottleneck: The generation of the secret fixed-weight vectors is a critical point for side-channel attacks, as it directly handles secret key material.

Mitigating Side-Channel Attacks in Fixed-Weight Vector Generation

The initial algorithm for generating fixed-weight vectors used rejection sampling, which resulted in a non-constant time execution. This vulnerability was exploited in a timing attack that could recover parts of the secret key. To address this, two constant-time solutions were implemented and compared:

• Fast, Non-Biased Method: This approach pre-fetches a larger-than-required number of random bits from a PRNG into a block RAM. It then iterates over the entire memory, regardless of when the required weight is achieved, ensuring a constant execution time. The downside is a small, parameter-dependent probability of failure if the pre-fetched bits are exhausted.
• Constant Weight Word Method: This is an algorithmic fix proposed by the HQC team. It avoids rejection sampling by reducing random bits into a different field and uses a clever replacement mechanism to handle duplicate indices. While this method introduces a negligible bias, it is algorithmically guaranteed to be constant-time and is now the recommended approach in the official specification.

The hardware design supports both methods, with the first being faster but the second offering a stronger security guarantee.

Optimizing the Performance Bottleneck: Polynomial Multiplication

Standard polynomial multiplication techniques like Schoolbook (O(n²)) or even Karatsuba (O(n¹⁵⁸⁵)) are too slow given the large polynomial degrees in HQC. The key insight for optimization is that one of the input polynomials is always sparse with a fixed, small weight (w).

A specialized sparse multiplication algorithm was designed, which leverages this property. Instead of performing a full multiplication, it shifts the non-sparse polynomial based on the indices of the non-zero elements of the sparse polynomial and accumulates the results. This reduces the complexity to O(n * w), a significant improvement.

The hardware realization includes:

• A parameterized variable shifter to perform the multiplication.
• Interleaved reduction logic that folds the result back into the field (F_2[x]/(x^n - 1)) on-the-fly, which saves significant memory and area.

While NTT/FFT-style multiplication is popular in lattice-based cryptography, it is not directly applicable to HQC’s binary field. A workaround using “Frobenius Additive FFTs” exists but incurs substantial overhead from basis conversions, making the dedicated sparse multiplier a much more efficient solution for HQC.

Results and Future Work

The resulting hardware implementation demonstrates significant speed-ups for Key Generation, Encapsulation, and Decapsulation compared to optimized software implementations using AVX instructions. The design also compares favorably to other hardware implementations in terms of the time-area product.

Ongoing work is exploring power side-channel attacks, specifically Correlation Power Analysis (CPA) on the variable shifter used in the sparse multiplier. The attack aims to recover the secret key by observing memory access patterns. Potential countermeasures being investigated include:

• Masking: A common but expensive technique that duplicates the design.
• Shuffling: Randomizing the order of the secret indices for each operation.
• Shifting: Applying a random offset to the sparse polynomial before computation.

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