Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware

Thomas Pöppelmann, Tim Güneysu

Progress in Cryptology - LATINCRYPT 2012 - 2nd International Conference on Cryptology and Information Security in Latin America, Santiago, Chile, October 7-10, 2012


In recent years lattice-based cryptography has emerged as quantum secure and theoretically elegant alternative to classical cryptographic schemes (like ECC or RSA). In addition to that, lattices are a versatile tool and play an important role in the development of efficient fully or somewhat homomorphic encryption (SHE/FHE) schemes. In practice, ideal lattices defined in the polynomial ring $mathbb{Z}_p[{bf x}]/langle {x}^n+1rangle$ allow the reduction of the generally very large key sizes of lattice constructions. Another advantage of ideal lattices is that polynomial multiplication is a basic operation that has, in theory, only quasi-linear time complexity of $Oh(n log{n})$ in $mathbb{Z}_p[{bf x}]/langle {x}^n+1rangle$. However, few is known about the practical performance of the FFT in this specific application domain and whether it is really an alternative. In this work we make a first step towards efficient FFT-based arithmetic for lattice-based cryptography and show that the FFT can be implemented efficiently on reconfigurable hardware. We give instantiations of recently proposed parameter sets for homomorphic and public-key encryption. In a generic setting we are able to multiply polynomials with up to 4096 coefficients and a 17-bit prime in less than 0.5 milliseconds. For a parameter set of a SHE scheme (n=1024,p=1061093377) our implementation performs 9063 polynomial multiplications per second on a mid-range Spartan-6.

[BibTeX] [DOI] [PDF]