SWIFFT: a modest proposal for FFT hashing. (English) Zbl 1154.68403

Lyubashevsky, Vadim; Micciancio, Daniele; Peikert, Chris; Rosen, Alon

Nyberg, Kaisa (ed.), Fast software encryption. 15th international workshop, FSE 2008, Lausanne, Switzerland, February 10–13, 2008. Revised selected papers. Berlin: Springer (ISBN 978-3-540-71038-7/pbk). Lecture Notes in Computer Science 5086, 54-72 (2008).

Summary: 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.
For the entire collection see [Zbl 1144.68007].

MSC:

94A60	Cryptography
65T50	Numerical methods for discrete and fast Fourier transforms
68P25	Data encryption (aspects in computer science)
68N99	Theory of software

Keywords:

compression functions

Software:

SWIFFT; NTRU