SWIFFT: A Modest Proposal for FFT Hashing

The authors propose SWIFFT, a collection of compression functions that are highly parallelizable and admit very efficient implementations on modern microprocessors. The main technique under-lying the functions is a novel use of the Fast Fourier Transform (FFT) to achieve "Diffusion," together with a linear combination to achieve compression and "Confusion." They 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 the implementation is competitive with that of SHA-256, with additional parallelism yet to be exploited.