Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
SWIFFT: A Modest Proposal for FFT Hashing
verfasst von : Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen
Erschienen in: Fast Software Encryption
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
.