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

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].

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 |