Low-cost and area-efficient FPGA implementations of lattice-based cryptography

Abstract

The interest in lattice-based cryptography is increasing due to its quantum resistance and its provable security under some worst-case hardness assumptions. As this is a relatively new topic, the search for efficient hardware architectures for lattice-based cryptographic building blocks is still an active area of research. We present area optimizations for the most critical and computationally-intensive operation in lattice-based cryptography: polynomial multiplication with the Number Theoretic Transform (NTT). The proposed methods are implemented on an FPGA for polynomial multiplication over the ideal ℤ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> [x]〈x <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> + 1〉. The proposed hardware architectures reduce slice usage, number of utilized memory blocks and total memory accesses by using a simplified address generation, improved memory organization and on-the-fly operand generations. Compared to prior work, with similar performance the proposed hardware architectures can save up to 67% of occupied slices, 80% of used memory blocks and 60% of memory accesses, and can fit into smallest Xilinx Spartan-6 FPGA.