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 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. 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. Unlike many other provably secure hash functions, the algorithm is quite fast, yielding a throughput of 40Mbit/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 is as follows: 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 Z p n {displaystyle mathbb {Z} _{p}^{n}} , which has size p n = 257 64 {displaystyle p^{n}=257^{64}} . An output in Z p n {displaystyle mathbb {Z} _{p}^{n}} can easily be represented using 528 bits (66 bytes). The SWIFFT functions can be described as a simple algebraic expression over some polynomial ring R {displaystyle R} . A family of these functions depends on three main parameters: let n {displaystyle n} be a power of 2, let m > 0 {displaystyle m>0} be a small integer, and let p > 0 {displaystyle p>0} be a modulus (not necessarily prime, but is convenient to choose it prime). Define R {displaystyle R} to be the ring R = Z p [ α ] / ( α n + 1 ) {displaystyle R=mathbb {Z} _{p}/(alpha ^{n}+1)} , i.e., the ring of polynomials in α {displaystyle alpha } having integer coefficients, modulo p {displaystyle p} and α n + 1 {displaystyle alpha ^{n}+1} . An element of R {displaystyle R} can be written as a polynomial of degree < n {displaystyle <n} having coefficients in Z p {displaystyle Z_{p}} . A certain function in the SWIFFT family is specified by m {displaystyle m} fixed elements a 1 , … , a m ∈ R {displaystyle a_{1},ldots ,a_{m}in R} of the ring R {displaystyle R} , that are called multipliers. The function corresponds to the following equation over the ring R: ∑ i = 1 m ( a i ⋅ x i ) {displaystyle sum _{i=1}^{m}(a_{i}cdot x_{i})} The x 1 , … , x m ∈ R {displaystyle x_{1},ldots ,x_{m}in R} are polynomials with binary coefficients, and corresponding to the binary input of length m n {displaystyle mn} . To compute the above expression, the main problem is to compute the polynomial products a i ⋅ x i {displaystyle 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: