SWIFFT: a modest proposal for FFT hashing

Authors: Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen.

Fast Software Encryption - FSE 2008, Lausanne, Switzerland (February 2008). pp. 54-72. LNCS 5086, Springer. doi:10.1007/978-3-540-71039-4_4

[BibTex] [Postscript] [PDF]. Code an instructions available on [GitHub].

Abstract: We propose SWIFFT, a collection of compression functions that are highly parallelizable and admit very efficient implementations on modern microprocessors. The main technique underlying our functions is a novel use of the Fast Fourier Transform (FFT) to achieve "diffusion," together with a linear combination to achieve compression and "confusion." We provide a detailed security analysis of concrete instantiations, and give a high-performance software implementation that exploits the inherent parallelism of the FFT algorithm. The throughput of our implementation is competitive with that of SHA-256, with additional parallelism yet to be exploited. Our functions are set apart from prior proposals (having comparable efficiency) by a supporting asymptotic security proof: it can be formally proved that finding a collision in a randomly-chosen function from the family (with noticeable probability) is at least as hard as finding short vectors in cyclic/ideal lattices in the worst case.

Notes: SWIFFT is the basis of the SWIFFTX NIST SHA3 candidate described in this report by Arbitman, Dogon, Lyubashevsky, Micciancio, Peikert and Rosen. The full SWIFFTX NIST SHA3 submission packet is available here.