SWIFFT is not the first hash function based on the FFT, but it sets itself apart by providing a mathematical proof of its security.
Unlike many other provably secure hash functions, the algorithm is quite fast, yielding a throughput of 40 Mbit/s on a 3.2 GHz Intel Pentium 4.
Therefore, its practical use would lie mostly in applications where the proof of collision-resistance is particularly valuable, such as digital signatures that must remain trustworthy for a long time.
[2] The algorithm is as follows:[3] The FFT operation in step 4 is easy to invert, and is performed to achieve diffusion, that is, to mix the input bits.
Assuming the parameters (n, m, p) = (64, 16, 257), any fixed compression function in the family takes a binary input of length mn = 1024 bits (128 bytes) to an output in the range ℤnp, which has size pn = 25764.
The SWIFFT functions can be described as a simple algebraic expression over some polynomial ring R. A family of these functions depends on three main parameters: let n be a power of 2, let m > 0 be a small integer, and let p > 0 be a modulus (not necessarily prime, but is convenient to choose it prime).
The parameters m, p, and n are subject to the following restrictions: A possible choice is (n,m,p) = (64,16,257), which achieves a throughput of about 40 Mbit/s, security of about 2106 operations for finding collisions, and a digest size of 512 bits.
Note that this means that the security of SWIFFT relies strongly on the difficulty of this mathematical problem.
It can be proven that the following holds: Suppose we have an algorithm that, for a random version of SWIFFT given by f, can find collisions in f within some feasible time T, and with probability p. It is allowed that the algorithm only works in a small but noticeable fraction of the SWIFFT family.