SWIFFT

In cryptography, SWIFFT is a collection of provably secure hash functions. It is based on the concept of the fast Fourier transform (FFT). SWIFFT is not the first hash function based on the FFT, but it sets itself apart by providing a mathematical proof of its security. It also uses the LLL basis reduction algorithm. It can be shown that finding collisions in SWIFFT is at least as difficult as finding short vectors in cyclic/ideal lattices in the worst case. By giving a security reduction to the worst-case scenario of a difficult mathematical problem, SWIFFT gives a much stronger security guarantee than most other cryptographic hash functions.

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. Although SWIFFT satisfies many desirable cryptographic and statistical properties, it was not designed to be an "all-purpose" cryptographic hash function. For example, it is not a pseudorandom function, and would not be a suitable instantiation of a random oracle. The algorithm is less efficient than most traditional hash functions that do not give a proof of their collision-resistance. 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.

A modification of SWIFFT called SWIFFTX was proposed as a candidate for SHA-3 function to the NIST hash function competition and was rejected in the first round.

The algorithm

The algorithm is as follows:

1. Let the polynomial variable be called Template:Mvar.
2. Input: message Template:Mvar of length Template:Math
3. Convert Template:Mvar to a collection of polynomials Template:Math in a certain polynomial ring Template:Mvar with binary coefficients.
4. Compute the Fourier coefficients of each Template:Math using SWIFFT.
5. Define the Fourier coefficients of Template:Math, so that they are fixed and depend on a family of SWIFFT.
6. Point-wise multiply the Fourier coefficients Template:Math with the Fourier coefficients of Template:Math for each Template:Mvar.
7. Use inverse FFT to obtain Template:Mvar polynomials Template:Math of degree Template:Math.
8. Compute $f=\sum _{i=1}^m(f_i)$ modulo Template:Mvar and Template:Math.
9. Convert Template:Mvar to Template:Math bits and output it.

The FFT operation in step 4 is easy to invert, and is performed to achieve diffusion, that is, to mix the input bits. The linear combination in step 6 achieves confusion, since it compresses the input. This is just a high level description of what the algorithm does, some more advanced optimizations are used to finally yield a high performing algorithm.

Example

Assuming the parameters Template:Math, any fixed compression function in the family takes a binary input of length Template:Math bits (128 bytes) to an output in the range Template:Math, which has size Template:Math. An output in Template:Math can easily be represented using 528 bits (66 bytes).

Algebraic description

The SWIFFT functions can be described as a simple algebraic expression over some polynomial ring Template:Mvar. A family of these functions depends on three main parameters: let Template:Mvar be a power of 2, let Template:Math be a small integer, and let Template:Math be a modulus (not necessarily prime, but is convenient to choose it prime). Define Template:Mvar to be the ring Template:Math, i.e., the ring of polynomials in Template:Mvar having integer coefficients, modulo Template:Mvar and Template:Math. An element of Template:Mvar can be written as a polynomial of degree Template:Math having coefficients in Template:Math. A certain function in the SWIFFT family is specified by Template:Mvar fixed elements Template:Math of the ring $R$, that are called multipliers. The function corresponds to the following formula over Template:Mvar:

$\sum _{i=1}^m(a_i\cdot x_i)$

The Template:Math are polynomials with binary coefficients, and corresponding to the binary input of length Template:Math.

Computing the polynomial product

To compute the above expression, the main problem is to compute the polynomial products Template:Math. A fast way to compute these products is given by the convolution theorem. This says that under certain restrictions, Template:Math, where Template:Math denotes the Fourier transform and Template:Math denotes the pointwise product. In the general case of the convolution theorem, Template:Math does not denote multiplication but convolution. It can, however, be shown that polynomial multiplication is a convolution.

Fast Fourier transform

The fast Fourier transform is used to find the Fourier coefficients of each polynomial, which are then multiplied point-wise with the respective Fourier coefficients of the other polynomial. The resulting coefficients are then transformed to a polynomial of degree Template:Math using an inverse fast Fourier transform.

Number-theoretic transform

Instead of the normal Fourier transform, SWIFFT uses the number-theoretic transform. The number-theoretic transform uses roots of unity in Template:Math instead of complex roots of unity. In order for this to work, Template:Math needs to be a finite field and primitive Template:Math^th roots of unity need to exist in this field. This can be done by taking Template:Mvar prime such that Template:Math divides Template:Math.

Parameter choice

The parameters Template:Mvar, Template:Mvar, and Template:Mvar are subject to the following restrictions:

• Template:Mvar must be a power of 2,
• Template:Mvar must be prime,
• Template:Math must be a multiple of Template:Math, and
• Template:Math (otherwise the output will not be smaller than the input).

A possible choice is Template:Math, which achieves a throughput of about 40 Mbit/s, security of about Template:Math operations for finding collisions, and a digest size of 512 bits.

Statistical properties

• Universal hashing. The SWIFFT family of functions is universal. This means that for any fixed distinct Template:Mvar and Template:Mvar, the probability (over the random choice of Template:Mvar from the family) that Template:Math is the inverse of the size of the range.
• Regularity. The SWIFFT family of compression functions is regular. A function Template:Mvar is said to be regular if, for an input Template:Mvar chosen uniformly at random from the domain, the output Template:Math is distributed uniformly over the range.
• Randomness extractor. SWIFFT is a randomness extractor. For hash tables and related applications, it is usually desirable for the outputs of the hash function to be distributed uniformly (or as close to uniformly as possible), even when the inputs are not uniform. Hash functions that give such guarantees are known as randomness extractors, because they distill the non-uniform randomness of the input down to an (almost) uniformly distributed output. Formally, randomness extraction is actually a property of a family of functions, from which one function is chosen at random (and obliviously to the input).

Cryptographic properties and security

• SWIFFT is not pseudorandom, due to linearity. For any function Template:Mvar from our family and any two inputs Template:Mvar and Template:Mvar such that Template:Math is also a valid input, we have that Template:Math. This relation is very unlikely to hold for a random function, so an adversary can easily distinguish our functions from a random function.
• It is not claimed by the authors that SWIFFT functions behave like a random oracle. A function is said to behave like a random oracle if it acts like a truly random function. This differs from pseudorandomness in that the function is fixed and public.
• The SWIFFT family is provably collision resistant (in an asymptotic sense), under a relatively mild assumption about the worst-case difficulty of finding short vectors in cyclic/ideal lattices. This implies that the family is also second preimage resistant.

Theoretical security

SWIFFT is an example of a provably secure cryptographic hash function. As with most security proofs, the security proof of SWIFFT relies on a reduction to a certain difficult-to-solve mathematical problem. Note that this means that the security of SWIFFT relies strongly on the difficulty of this mathematical problem.

The reduction in the case of SWIFFT is to the problem of finding short vectors in cyclic/ideal lattices. It can be proven that the following holds: Suppose we have an algorithm that, for a random version of SWIFFT given by Template:Mvar, can find collisions in Template:Mvar within some feasible time Template:Mvar, and with probability Template:Mvar. It is allowed that the algorithm only works in a small but noticeable fraction of the SWIFFT family. Then we can find also an algorithm Template:Math which can always find a short vector in any ideal lattice over the ring Template:Math in some feasible time Template:Math, depending on Template:Mvar and Template:Mvar. This means that finding collisions in SWIFFT is at least as difficult as the worst-case scenario of finding short vectors in a lattice over Template:Math. At the momentTemplate:When, the fastest algorithms for finding short vectors are all exponential in Template:Mvar. Note that this ensures that there is no significant set of "weak instances" where the security of SWIFFT is weak. This guarantee is not given by most other provably secure hash functions.

Practical security

Known working attacks are the generalized birthday attack, which takes 2¹⁰⁶ operations, and inversion attacks which takes 2⁴⁴⁸ operations for a standard parameter choice. This is usually considered to be enough to render an attack by an adversary infeasible.