Abstract
With the surge of powerful quantum computers, lattice-based cryptography has proliferated in recent hardware implementations due to its resistance against quantum-based attacks. 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 reduces overall resource consumption by reusing the multipliers and adders within the modular polynomial computation unit. Experimental results show that the proposed design effectively reduces DSP usage, particularly for the discrete Ziggurat sampling method.
Introduction
As the cryptographic community prepares for the post-quantum era, lattice-based schemes have emerged as leading candidates for standardization. However, the transition to these algorithms presents significant hardware challenges. Implementing lattice-based cryptography on Field Programmable Gate Arrays (FPGAs) is traditionally resource-intensive, primarily due to two distinct computational bottlenecks: modular polynomial multiplication and discrete Gaussian sampling.
Modular polynomial multiplication is typically accelerated using the Number Theoretic Transform (NTT), while Gaussian sampling is required to generate the noise that underpins the security of Learning With Errors (LWE) problems. Historically, these two components have been designed as independent modules. This separation leads to hardware redundancy, as the sampler requires its own dedicated Digital Signal Processing (DSP) slices and Look-Up Tables (LUTs), even though the NTT unit often sits idle during the sampling phase. This paper introduces an "integral architecture" that bridges this gap through strategic resource sharing.
The Integral Architecture Approach
The core innovation of this work is the transformation of the sampler from a standalone computational block into a control module that "borrows" the arithmetic logic of the polynomial multiplier. This is made possible by a key observation regarding the temporal flow of cryptographic protocols: in most encryption and key-generation sequences, error sampling occurs before polynomial multiplication. This temporal separation allows a single set of hardware resources to serve two roles sequentially.
Hardware Reconfiguration
To facilitate this reuse, the authors modified the standard "butterfly units" within the NTT module. By introducing multiplexers (MUXes), the architecture can be reconfigured on the fly. In multiplication mode, the units perform standard modular arithmetic. In sampling mode, the units are bypassed or cascaded to function as general-purpose adders and multipliers.
Algorithm Integration
The research demonstrates the versatility of this integral approach by applying it to two distinct sampling algorithms:
- Knuth-Yao Algorithm: This tree-based method requires frequent bit-length additions for tree traversal. The integral architecture reuses the NTT’s adders to handle these operations, reducing the need for dedicated logic gates.
- Discrete Ziggurat Algorithm: This rejection sampling method is more complex and requires high-precision linear interpolation (the
sLineoperation). To accommodate 64-bit multiplications within the narrower bit-width of a standard NTT unit (e.g., 12-bit), the authors implemented a multi-bit partitioning strategy. The large multiplication is broken into smaller chunks that fit the NTT multipliers, with the partial results summed using the existing NTT adders.
Experimental Evaluation
The architecture was evaluated using parameters from two representative lattice-based systems: standard LWE ($\sigma = 3.33, q = 4093, n = 256$) and the BLISS digital signature scheme ($\sigma = 215.73, q = 12289, n = 512$). The designs were implemented on a Xilinx Artix-7 AC701 evaluation board.
Resource Efficiency
The results indicate substantial hardware savings without compromising clock speed. The most significant impact was observed in the Ziggurat sampler for BLISS parameters:
- DSP Reduction: A standalone Ziggurat sampler required 16 DSPs. The integrated version reduced this requirement to just 2 DSPs—an 87.5% reduction in the sampler's specific DSP footprint.
- Logic Savings: The Knuth-Yao implementation showed a marked reduction in LUTs and Flip-Flops (FFs) as the primary arithmetic workload was offloaded to the NTT unit.
- Performance: Both integrated architectures maintained an operating frequency of 100MHz, matching the performance of standalone versions.
Conclusion and Future Work
The integral architecture proves that the hardware cost of a sampler can be reduced primarily to control logic and routing overhead by leveraging existing arithmetic units. While this approach introduces a structural hazard—sampling and multiplication cannot occur simultaneously—it offers a highly efficient solution for area-constrained applications where sequential processing is acceptable.
Future research may extend this "integral" philosophy to other components of Post-Quantum Cryptography (PQC) hardware, such as hash modules or Keccak engines, further optimizing the footprint of quantum-resistant security modules.
Summary updated