SWIFFT
Encyclopedia
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
and was rejected in the first round.
, which has size 
. An output in 
can easily be represented using 528 bits (66 bytes).
. A family of these functions depends on three main parameters: let 
be a power of 2, let 
be a small integer, and let 
be a modulus (not necessarily prime
, but is convenient to choose it prime). Define
to be the ring 
, i.e., the ring of polynomials in 
having integer coefficients, modulo 
and 
. An element of 
can be written as a polynomial of degree 
having coefficients in 
. A certain function in the SWIFFT family is specified by 
fixed elements 
of the ring 
, that are called multipliers. The function corresponds to the following equation over the ring R:
The
are polynomials with binary coefficients, and corresponding to the binary input of length 
.
. A fast way to compute these products is given by the convolution theorem
. This says that under certain restrictions the following holds:
Here
denotes the Fourier transform
and
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.
) which finds the transform in
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
.
instead of complex roots of unity. To make this work, we need to ensure that 
is a field
, and that primitive 2nth roots of unity exist in this field. This can be done by taking
prime such that 
divides 
.
A possible choice is n=64, m=16, p=257. We get a throughput of about 40MB/s, security of about
operations for finding collisions, and a digest size of 512 bits.
. 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
can find collisions in 
within some feasible time 
, and with probability 
. 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 
which can always find a short vector in any ideal lattice over the ring 
in some feasible time 
, depending on 
and 
.
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
. At the moment the fastest algorithms for finding short vectors are all exponential in 
. 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.
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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, SWIFFT is a collection of provably secure
Provably secure cryptographic hash function
In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, complexity theory and formal reduction. These...
hash functions
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
. It is based on the concept of the Fast Fourier Transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
(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
Ideal lattice cryptography
Ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as...
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
Provably secure cryptographic hash function
In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, complexity theory and formal reduction. These...
.
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
Pseudorandom function
In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish between a function chosen randomly from the PRF family and a random oracle...
, and would not be a suitable instantiation of a random oracle
Random oracle
In cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
. 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
NIST hash function competition
The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology for a new SHA-3 function to replace the older SHA-1 and SHA-2, which was formally announced in the Federal Register on November 2, 2007...
and was rejected in the first round.
The Algorithm
The algorithm is as follows:- Let the polynomialPolynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
variable be called
- Input: message
of length 
- Convert
to a collection of 
polynomials 
in a certain polynomial ringPolynomial ringIn mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the Hilbert basis theorem, to the construction of...
with binary coefficients. - Compute the Fourier coefficients of each
using SWIFFT. - Define the Fourier coefficients of
, so that they are fixed and depend on a family of SWIFFT. - Point-wise multiply the Fourier coefficients
with the Fourier coefficients of 
for each 
. - Use inverse FFT to obtain
polynomials 
of degree 
. - Compute
modulo 
and 
. - Convert
to 
bits and output it.
- The FFTFast Fourier transformA fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
operation in step 4 is easy to invert, and is performed to achieve diffusionConfusion and diffusionIn cryptography, confusion and diffusion are two properties of the operation of a secure cipher which were identified by Claude Shannon in his paper Communication Theory of Secrecy Systems, published in 1949....
, that is, to mix the input bits. - The linear combinationLinear combinationIn mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...
in step 6 achieves confusionConfusion and diffusionIn cryptography, confusion and diffusion are two properties of the operation of a secure cipher which were identified by Claude Shannon in his paper Communication Theory of Secrecy Systems, published in 1949....
, 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
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, which has size . An output in 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 ringPolynomial ring
In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the Hilbert basis theorem, to the construction of...
. A family of these functions depends on three main parameters: let be a power of 2, let be a small integer, and let be a modulus (not necessarily primePrime
A prime is a natural number that has exactly two distinct natural number divisors: 1 and itself.Prime or PRIME may also refer to:In mathematics:*Prime , the ′ mark, typically used as a suffix...
, but is convenient to choose it prime). Define
to be the ring , i.e., the ring of polynomials in having integer coefficients, modulo and . An element of can be written as a polynomial of degree having coefficients in . A certain function in the SWIFFT family is specified by fixed elements of the ring , that are called multipliers. The function corresponds to the following equation over the ring R:The
are polynomials with binary coefficients, and corresponding to the binary input of length .Computing the polynomial product
To compute the above expression, the main problem is to compute the polynomial products. A fast way to compute these products is given by the convolution theoremConvolution theorem
In mathematics, the convolution theorem states that under suitableconditions the Fourier transform of a convolution is the pointwise product of Fourier transforms. In other words, convolution in one domain equals point-wise multiplication in the other domain...
. This says that under certain restrictions the following holds:
Here
denotes the Fourier transformFourier transform
In mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...
and
denotes the pointwise product. In the general case of the convolution theorem does not denote multiplication but convolutionConvolution
In mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...
. 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 TransformFast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
) which finds the transform in
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
.Number-theoretic transform
Instead of the normal Fourier transform SWIFFT uses the Number-theoretic transform. Number-theoretic transform uses roots of unity in instead of complex roots of unity. To make this work, we need to ensure that is a fieldField
-Places:* Field, British Columbia, Canada* Field, Minneapolis, Minnesota, United States* Field, Ontario, Canada* Field Island, Nunavut, Canada* Mount Field - Expanses of open ground :* Field...
, and that primitive 2nth roots of unity exist in this field. This can be done by taking
prime such that divides .Parameter Choice
The parameters m,p,n are subject to the following restrictions:- n must be a power of 2
- p must be prime
- p-1 must be a multiple of 2n
-
must be greater than m (otherwise the output will not be smaller than the input)
A possible choice is n=64, m=16, p=257. We get a throughput of about 40MB/s, security of about
operations for finding collisions, and a digest size of 512 bits.Statistical Properties
- (Universal hashing). The SWIFFT family of functions is universalUniversal hashingUsing universal hashing refers to selecting a hash function at random from a family of hash functions with a certain mathematical property . This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary...
. It means that for any fixed distinct
, the probability (over the random choice of 
from the family) that 
is the inverse of the size of the range. - (Regularity). SWIFFT family of compression functions is regular. A function
is said to be regular if, for an input 
chosen uniformly at random from the domain, the output 
is distributed uniformly over the range.
- (Randomness extractor). SWIFFT is a randomness extractorRandomness extractorA randomness extractor, often simply called "an extractor," is a function which, when applied to a high-entropy source , generates a random output that is shorter, but uniformly distributed...
. 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 extractorRandomness extractorA randomness extractor, often simply called "an extractor," is a function which, when applied to a high-entropy source , generates a random output that is shorter, but uniformly distributed...
s, 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
from our family and any two inputs 
, 
such that 
is also a valid input, we have that 
. 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 oracleRandom oracleIn cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...
. 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. - SWIFFT family is provablyProvably secure cryptographic hash functionIn cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, complexity theory and formal reduction. These...
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 functionProvably secure cryptographic hash function
In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, complexity theory and formal reduction. These...
. As with most security proofs, the security proof of SWIFFT relies on a reduction
Polynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp 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
Ideal lattice cryptography
Ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as...
. It can be proven that the following holds:
Suppose we have an algorithm that for a random version of SWIFFT given by
can find collisions in within some feasible time , and with probability . 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 which can always find a short vector in any ideal lattice over the ring in some feasible time , depending on and .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
. At the moment the fastest algorithms for finding short vectors are all exponential in . 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 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.