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 adve ...
, 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
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 t ...
(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, 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 tha ...
. 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 ann ...
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 ex ...
variable be called
#Input: message
of length
#Convert
to a collection of
polynomials
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 variable ...
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
FFT 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
, 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 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 variable ...
. 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
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 way ...
, 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 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. ...
. This says that under certain restrictions the following holds:
:
Here
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
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 mathematical operation on two functions ( and ) that produces a third function (f*g) that expresses how the shape of one is modified by the other. The term ''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
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 t ...
) 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 use an inverse FFT to return a polynomial of degree
.
Number-theoretic transform
Instead of the normal Fourier transform, SWIFFT uses the
number-theoretic transform. The 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
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, subt ...
, and that primitive 2''n''
th 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 2''n''
*
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
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
, 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 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 random ...
, 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 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 tha ...
. 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. 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.
Practical security
Known working attacks are the
generalized birthday attack, which takes 2
106 operations and ''inversion attacks'' which takes 2
448 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