Title | ||
---|---|---|
Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware |
Abstract | ||
---|---|---|
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 ℤp[x]/〈xn+1〉 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 ${\mathcal O}(n \log{n})$ in ℤp[x]/〈xn+1〉. 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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-33481-8_8 | LATINCRYPT |
Keywords | Field | DocType |
basic operation,homomorphic encryption,reconfigurable hardware,ideal lattice,lattice-based cryptography,towards efficient arithmetic,theoretically elegant alternative,efficient fft-based arithmetic,public-key encryption,polynomial ring,parameter set,polynomial multiplication,fft,lattice based cryptography | Prime (order theory),Homomorphic encryption,Discrete mathematics,Polynomial,Polynomial ring,Cryptography,Arithmetic,Encryption,Fast Fourier transform,Lattice-based cryptography,Mathematics | Conference |
Citations | PageRank | References |
48 | 2.27 | 36 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Thomas Pöppelmann | 1 | 357 | 17.96 |
Tim Güneysu | 2 | 924 | 77.37 |