Integral Sampler and Polynomial Multiplication Architecture for Lattice-based Cryptography

Antian Wang, Weihang Tan, Keshab K. Parhi, Yingjie Lao

TL;DR

This paper introduces an "integral architecture" for lattice-based cryptography that reuses the hardware resources of a polynomial multiplier to perform Gaussian sampling. By reconfiguring the multipliers and adders already present in the Number Theoretic Transform (NTT) unit, the authors significantly reduce the hardware footprint—specifically slashing DSP usage for the Discrete Ziggurat sampler—without sacrificing performance.

What Problem Does This Paper Address?

Lattice-based cryptography is a leading candidate for the "Post-Quantum" era because it is resistant to attacks from quantum computers. However, implementing these schemes in hardware (like FPGAs) is resource-intensive. Two major computational bottlenecks are:

  1. Modular Polynomial Multiplication: Usually handled by a dedicated unit using the Number Theoretic Transform (NTT).
  2. Discrete Gaussian Sampling: Used to generate random errors that ensure the security of the scheme.

Traditionally, these two components are designed as separate, independent modules. This leads to redundant hardware; the sampler often requires its own set of expensive Digital Signal Processing (DSP) slices and logic gates (LUTs) to perform additions and multiplications, even though the NTT unit nearby sits idle during the sampling phase. The authors aim to bridge this gap through resource sharing.

Methods

The authors propose a novel Integral Architecture where the sampler is no longer a standalone block but a control module that "borrows" the arithmetic logic of the polynomial multiplier.

  • Hardware Reconfiguration: They use multiplexers (MUXes) to reconfigure the "butterfly units" within the NTT module. Depending on the operation mode, these units can perform standard modular arithmetic for multiplication or be bypassed/cascaded to act as general-purpose adders and multipliers for sampling.
  • Algorithm Integration: They demonstrate this approach on two widely used sampling algorithms:
  • Knuth-Yao Algorithm: A tree-based sampling method. The architecture reuses NTT adders to handle the bit-length additions required for tree traversal.
  • Discrete Ziggurat Algorithm: A more complex rejection sampling method. This algorithm requires high-precision linear interpolation (sLine operation). The authors partition these large multiplications into smaller chunks that fit the existing NTT multipliers, then sum the partial results using the NTT's adders.

Datasets

The architecture was evaluated using parameters from two representative lattice-based cryptosystems:

  • $\sigma_{LP} = 3.33, q = 4093, n = 256$: Typical for standard Learning With Errors (LWE) problems.
  • $\sigma_{BLISS} = 215.73, q = 12289, n = 512$: Parameters associated with the BLISS digital signature scheme.
  • Hardware Target: The designs were implemented and tested on an Xilinx Artix-7 AC701 evaluation board.

Key Insights and Ideas

  • Temporal Separation: In many cryptographic protocols (like key generation or encryption), the sampling of errors happens before the polynomial multiplication. This temporal gap is the "aha moment" that allows one piece of hardware to serve two roles sequentially.
  • Multi-bit Partitioning: To handle the high-precision requirements of the Ziggurat sampler (e.g., 64-bit multiplications) using smaller modular multipliers, the authors cleverly partitioned the operations into 12-bit partial multiplications, matching the bit-width of the underlying NTT unit.
  • Efficiency through Integration: By redesigning the sampler as a "control module" rather than a full computational unit, the authors proved that the "cost" of a sampler can be reduced primarily to control logic and a few MUXes.

Key Results

The experimental results demonstrate significant resource savings, particularly for the more complex Ziggurat sampler:

  • DSP Reduction: For the BLISS parameters, a standalone Ziggurat sampler required 16 DSPs. The proposed integrated sampler control module reduced this to just 2 DSPs—an 87.5% reduction in the sampler's specific DSP footprint.
  • Logic Savings: For the Knuth-Yao sampler, the integrated version showed a reduction in Look-Up Tables (LUTs) and Flip-Flops (FFs) compared to standalone versions, as the heavy lifting was offloaded to the NTT unit.
  • Performance Parity: Both the integrated Knuth-Yao and Ziggurat architectures maintained an operating frequency of 100MHz, proving that resource sharing does not necessarily lead to a slower clock speed.

Limitations and Future Work

  • Throughput Constraints: While this approach saves area, it creates a structural hazard: you cannot sample and multiply simultaneously. In ultra-high-throughput applications where these stages must be pipelined, this integral architecture might introduce latency.
  • Control Complexity: The paper notes that the reconfiguration logic (MUXes and state machines) adds some overhead, though it is negligible compared to the savings in DSPs.
  • Future Directions: The authors suggest that this "integral" philosophy could be extended to other components of Post-Quantum Cryptography (PQC) hardware, such as hash modules or different variants of the LWE problem.

Summary updated

Abstract

With the surge of the powerful quantum computer, lattice-based cryptography proliferated the latest cryptography hardware implementation due to its resistance against quantum computers. Among the computational blocks of lattice-based cryptography, the random errors produced by the sampler play a key role in ensuring the security of these schemes. This paper proposes an integral architecture for the sampler, which can reduce the overall resource consumption by reusing the multipliers and adders within the modular polynomial computation. For instance, our experimental results show that the proposed design can effectively reduce the discrete Ziggurat sampling method in DSP usage.
BibTeX
@inproceedings{wang2022integral,
  author = {Antian Wang and Weihang Tan and Keshab K. Parhi and Yingjie Lao},
  title = {{Integral Sampler and Polynomial Multiplication Architecture for Lattice-based Cryptography}},
  booktitle = {DFT},
  year = {2022},
  url = {https://openreview.net/forum?id=-uATSEwJh1},
}

Loading related content...

Figure