SWIFFT
   HOME

TheInfoList



OR:

In
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, SWIFFT is a collection of
provably secure Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields. Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabiliti ...
hash functions A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually ...
. 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 A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography: * the probability of a particular n-bit output ...
. 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 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 (with significant advantage) betwee ...
, and would not be a suitable instantiation of a
random oracle In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time th ...
. 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 The NIST hash function competition was an open competition held by the US National Institute of Standards and Technology (NIST) to develop a new hash function called SHA-3 to complement the older SHA-1 and SHA-2. The competition was formally an ...
and was rejected in the first round.


The algorithm

The algorithm is as follows: #Let the
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
variable be called \alpha #Input: message M of length mn #Convert M to a collection of m polynomials p_i in a certain
polynomial ring In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables) ...
R with binary coefficients. #Compute the Fourier coefficients of each p_i using SWIFFT. #Define the Fourier coefficients of a_i, so that they are fixed and depend on a family of SWIFFT. #Point-wise multiply the Fourier coefficients p_i with the Fourier coefficients of a_i for each i. #Use inverse FFT to obtain m polynomials f_i of degree <2n. #Compute f = \sum_^m (f_i) modulo p and \alpha^n+1. #Convert f to n\log(p) bits and output it. * The
FFT A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the ...
operation in step 4 is easy to invert, and is performed to achieve
diffusion Diffusion is the net movement of anything (for example, atoms, ions, molecules, energy) generally from a region of higher concentration to a region of lower concentration. Diffusion is driven by a gradient in Gibbs free energy or chemical p ...
, that is, to mix the input bits. * The linear combination in step 6 achieves
confusion In medicine, confusion is the quality or state of being bewildered or unclear. The term "acute mental 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

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^n_p , which has size p^n = 257^. An output in \mathbb^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 In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables) ...
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 A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
, but is convenient to choose it prime). Define R to be the ring R = \mathbb_p
alpha Alpha (uppercase , lowercase ; grc, ἄλφα, ''álpha'', or ell, άλφα, álfa) is the first letter of the Greek alphabet. In the system of Greek numerals, it has a value of one. Alpha is derived from the Phoenician letter aleph , whic ...
(\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 \mathbb_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_^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 In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the pointwise product of their Fourier transforms. More generally, convolution in one domain (e.g ...
. This says that under certain restrictions the following holds: : \mathcal\ = \mathcal\ \cdot \mathcal\ Here \mathcal denotes the
Fourier transform A Fourier transform (FT) is a mathematical transform that decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency. Most commonly functions of time or space are transformed, ...
and \cdot denotes the pointwise product. In the general case of the convolution theorem * does not denote multiplication but
convolution In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions ( and ) that produces a third function (f*g) that expresses how the shape of one is ...
. 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 A Fourier series () is a summation of harmonically related sinusoidal functions, also known as components or harmonics. The result of the summation is a periodic function whose functional form is determined by the choices of cycle length (or ''p ...
of each polynomial. Then we pointwise multiply the respective Fourier coefficients of the two polynomials, and finally we use 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. The number-theoretic transform uses roots of unity in \mathbb_p instead of complex roots of unity. To make this work, we need to ensure that \mathbb_p is a
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
, and that primitive 2''n''th 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: * ''n'' must be a power of 2 * ''p'' must be prime * ''p''-1 must be a multiple of 2''n'' * \log(p) must be smaller 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 40Mbit/s, security of about 2^ operations for finding collisions, and a digest size of 512 bits.


Statistical properties

* (Universal hashing). The SWIFFT family of functions is
universal Universal is the adjective for universe. Universal may also refer to: Companies * NBCUniversal, a media and entertainment company ** Universal Animation Studios, an American Animation studio, and a subsidiary of NBCUniversal ** Universal TV, a ...
. It means that for any fixed distinct x, x', the probability (over the random choice of f from the family) that f(x) = f(x') is the inverse of the size of the range. * (Regularity). SWIFFT family of compression functions is regular. A function f is said to be regular if, for an input x chosen uniformly at random from the domain, the output f(x) is distributed uniformly over the range. * (Randomness extractor). SWIFFT is a
randomness extractor A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent fro ...
. 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 extractor A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent fro ...
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 A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Background The generation of random numbers has many uses, such as for rand ...
, due to linearity. For any function f from our family and any two inputs x_1, x_2 such that x_1+x_2 is also a valid input, we have that f(x_1)+f(x_2) = f(x_1+x_2). 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 In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time th ...
. 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 provably collision resistant (in an asymptotic sense), under a relatively mild assumption about the
worst-case In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
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 In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on mathematical problems, and whose security thus follows from rigorous mathematical proofs, c ...
. 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_p
alpha Alpha (uppercase , lowercase ; grc, ἄλφα, ''álpha'', or ell, άλφα, álfa) is the first letter of the Greek alphabet. In the system of Greek numerals, it has a value of one. Alpha is derived from the Phoenician letter aleph , whic ...
(\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_p
alpha Alpha (uppercase , lowercase ; grc, ἄλφα, ''álpha'', or ell, άλφα, álfa) is the first letter of the Greek alphabet. In the system of Greek numerals, it has a value of one. Alpha is derived from the Phoenician letter aleph , whic ...
(\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 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.


References

{{Cryptography hash Cryptographic hash functions