SWIFFT

SWIFFT is a family of provably secure cryptographic hash functions built on the fast Fourier transform. Its distinguishing feature is a security proof: finding collisions in SWIFFT is shown to be at least as hard as finding short vectors in cyclic or ideal lattices in the worst case, which gives a stronger guarantee than most other hash functions offer. Input bits are converted into polynomials, transformed with a number-theoretic transform, multiplied point by point with fixed multiplier polynomials, transformed back, summed and reduced, which mixes the input and compresses it. A typical parameter choice takes 1024 input bits to a 512 bit digest at roughly 40 megabits per second on a 3.2 GHz Pentium 4. The functions are linear, so they are not pseudorandom and would not suit use as a random oracle, and they are slower than conventional hashes that carry no proof, so their natural use is where long term trust in collision resistance matters, such as digital signatures. A variant called SWIFFTX was submitted to the NIST hash function competition for SHA-3 and was rejected in the first round.