Paper 2012/343

High-Throughput Hardware Architecture for the SWIFFT / SWIFFTX Hash Functions

Tamas Gyorfi, Octavian Cret, Guillaume Hanrot, and Nicolas Brisebarre

Abstract

Introduced in 1996 and greatly developed over the last few years, Lattice-based cryptography oers a whole set of primitives with nice features, including provable security and asymptotic efficiency. Going from \asymptotic" to \real-world" efficiency seems important as the set of available primitives increases in size and functionality. In this present paper, we explore the improvements that can be obtained through the use of an FPGA architecture for implementing an ideal-lattice based cryptographic primitive. We chose to target two of the simplest, yet powerful and useful, lattice-based primitives, namely the SWIFFT and SWIFFTX primitives. Apart from being simple, those are also of central use for future primitives as Lyubashevsky's lattice-based signatures. We present a high-throughput FPGA architecture for the SWIFFT and SWIFFTX primitives. One of the main features of this implementation is an efficient implementation of a variant of the Fast Fourier Transform of order 64 on Z257. On a Virtex-5 LX110T FPGA, we are able to hash 0.6GB/s, which shows a ca. 16x speedup compared to SIMD implementations of the literature. We feel that this demonstrates the revelance of FPGA as a target architecture for the implementation of ideal-lattice based primitives.

Note: Authors names inserted