SWIFFT

SWIFFT
General
Designers Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen
First published 2008
Related to FFT-based algorithms

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 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 as 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 40MB/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[1] and was rejected in the first round.[2]

The Algorithm

The algorithm is as follows:[3]

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

Example

We choose concrete values for the parameters n, m, and p as follows: n = 64, m= 16, p= 257. For these parameters, any fixed compression function in the family takes a binary input of length mn = 1024 bits (128 bytes), to an output in the range  \mathbb{Z}^n_p , which has size  p^n = 257^{64}. An output in  \mathbb{Z}^n_p 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 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). Define R to be the ring R = \mathbb{Z}_p[\alpha]/(\alpha^n + 1), i.e., the ring of polynomials in \alpha having integer coefficients, modulo p and \alpha^n +1. An element of R can be written as a polynomial of degree < n having coefficients in Z_p. A certain function in the SWIFFT family is specified by m fixed elements a_1,\ldots,a_m \in R of the ring R, that are called multipliers. The function corresponds to the following equation over the ring R:

 \sum_{i=1}^m (a_i \cdot x_i)

The x_1,\ldots, x_m \in R are polynomials with binary coefficients, and corresponding to the binary input of length mn.

Computing the polynomial product

To compute the above expression, the main problem is to compute the polynomial products  a_i \cdot x_i . A fast way to compute these products is given by the convolution theorem. This says that under certain restrictions the following holds:

\mathcal{F}\{f*g\} = \mathcal{F}\{f\} \cdot \mathcal{F}\{g\}

Here \mathcal{F} denotes the Fourier transform and \cdot denotes the pointwise product. In the general case of the convolution theorem * does not denote multiplication but convolution. It can however be shown that polynomial multiplication is a convolution.

Fast Fourier Transform

For finding the Fourier transform we will use FFT (Fast Fourier Transform) which finds the transform in  O(n \log(n))time. The multiplication algorithm now goes as follows: We use FFT to compute (all at once) the Fourier coefficients of each polynomial. Then we pointwise multiply the respective Fourier coefficients of the two polynomials, and finally we us an inverse FFT to return a polynomial of degree < 2n.

Number-theoretic transform

Instead of the normal Fourier transform SWIFFT uses the Number-theoretic transform. Number-theoretic transform uses roots of unity in \mathbb{Z}_p instead of complex roots of unity. To make this work, we need to ensure that \mathbb{Z}_p is a finite field, and that primitive 2nth roots of unity exist in this field. This can be done by taking p prime such that 2n divides p-1.

Parameter Choice

The parameters m,p,n are subject to the following restrictions:

A possible choice is n=64, m=16, p=257. We get a throughput of about 40MB/s, security of about 2^{106} operations for finding collisions, and a digest size of 512 bits.

Statistical Properties

Cryptographic Properties and Security

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 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 family SWIFFT. Then we can find also an algorithm f_2 which can always find a short vector in any ideal lattice over the ring \mathbb{Z}_p[\alpha]/(\alpha^n + 1) in some feasible time T_2, depending on T and p. 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 \mathbb{Z}_p[\alpha]/(\alpha^n + 1). At the moment the fastest algorithms for finding short vectors are all exponential in n. 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: Generalized Birthday Attack, which takes 2106 operations and inversion attacks which takes 2448 operations for a standard parameter choice. This is usually considered to be enough to render an attack by an adversary infeasible.

Notes

  1. Daniele Micciancio; Yuriy Arbitman; Gil Dogon; Vadim Lyubashevsky; Chris Peikert; Alon Rosen. "SWIFFTX: A Proposal for the SHA-3 Standard" (PDF). Retrieved 2008-11-18.
  2. "Second Round Candidates". National Institute of Standards and Technology. January 19, 2010. Retrieved February 14, 2010.
  3. "SWIFFT: A Modest Proposal for FFT Hashing"

References

This article is issued from Wikipedia - version of the Saturday, April 02, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.