A Family of Scalable Polynomial Multiplier Architectures for Lattice-Based Cryptography

Lattice based cryptography is considered as an important candidate for post-quantum cryptosystems. Various lattice based cryptosystems are based on the Ring learning with errors (Ring-LWE) problem. As a basic operation of Ring-LWE problem, polynomial multiplication over rings is the most critical and computationally intensive operation of these cryptosystems. In this paper, we exploit the number theoretic transform (NTT) to build a family of scalable polynomial multiplier architectures, which provide designers with a trade-off choice of speed vs. area. Our multiplier architectures reduce the required clock cycles from 8n+1.5n lg n) to (2n+1.5n lg n/B), where n is the dimension of the polynomials and B is number of butterfly operators. The experimental results on a Spartan-6 FPGA show that our proposed polynomial multiplier (B = 2) achieves a speedup of 2.5 times on average and consumes less slices and block RAMs when compared with the state of art of compact design. On a Stratix FPGA, our polynomial multiplier (B = 4) is able to achieve a speedup of 1.2 times on average and save around 90% Memory ALUTs, 75% block memory bits, and 63% DSPs when compared with the state of art of high speed design. On a Spartan-6 FPGA, our polynomial multiplier (B = 8) is capable to calculate the product of two polynomials of degree 256/512/1024/2048 in 2.88/5.71/11.46/24.89 μs.