First published 2008 | Related to | |
Designers Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen |
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 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.
Contents
- The Algorithm
- Example
- Algebraic description
- Computing the polynomial product
- Fast Fourier Transform
- Number theoretic transform
- Parameter Choice
- Statistical Properties
- Cryptographic Properties and Security
- Theoretical Security
- Practical Security
- References
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 and was rejected in the first round.
The Algorithm
The algorithm is as follows:
- Let the polynomial variable be called
α - Input: message
M of lengthm n - Convert
M to a collection ofm polynomialsp i R with binary coefficients. - Compute the Fourier coefficients of each
p i - Define the Fourier coefficients of
a i - Point-wise multiply the Fourier coefficients
p i a i i . - Use inverse FFT to obtain
m polynomialsf i < 2 n . - Compute
f = ∑ i = 1 m ( f i ) modulop andα n + 1 . - Convert
f ton 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
Algebraic description
The SWIFFT functions can be described as a simple algebraic expression over some polynomial ring
The
Computing the polynomial product
To compute the above expression, the main problem is to compute the polynomial products
Here
Fast Fourier Transform
For finding the Fourier transform we will use FFT (Fast Fourier Transform) which finds the transform in
Number-theoretic transform
Instead of the normal Fourier transform SWIFFT uses the Number-theoretic transform. Number-theoretic transform uses roots of unity in
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
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
Practical Security
Known working attacks are the 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.