Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware
Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware
复制标题
DOI：
10.1007/978-3-642-33481-8_8
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
T. Pöppelmann;Tim Güneysu
中科院分区：
文献类型：
--
作者：
T. Pöppelmann;Tim Güneysu
近年来，基于格的密码学已成为经典密码方案（如 ECC 或 RSA）的量子安全且理论上优雅的替代方案。除此之外，格是一种多功能工具，在开发高效的完全或部分同态加密（SHE/FHE）方案中发挥着重要作用。实际上，多项式环 ℤp[x]/<xn+ 1> 中定义的理想格允许减小格结构中通常非常大的密钥尺寸。理想格的另一个优点是多项式乘法是一种基本运算，理论上只有准线性时间复杂度in ℤp[x]/<xn+ 1>。然而，人们对 FFT 在这个特定应用领域的实际性能以及它是否真的是一种替代方案知之甚少。在这项工作中，我们朝着基于格的密码学的高效基于 FFT 的算法迈出了第一步，并表明 FFT 可以在可重新配置的硬件上有效地实现。我们给出了最近提出的同态和公钥加密参数集的实例。在一般设置中，我们能够在不到 0.5 毫秒的时间内将具有最多 4096 个系数和 17 位素数的多项式相乘。对于 SHE 方案的参数集 (n=1024，p=1061093377)，我们的实现在中档 Spartan-6 上每秒执行 9063 次多项式乘法。
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 ofin ℤ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.