Swift

Swift
Swift
Developers	Vadim Lyubashevsky, Daniel Michianchio, Chris Peikert, Alon Rosen
Created by	2008
Published	2008
Type of	hash function

SWIFFT is a set of cryptographic hash functions with proven robustness ^[1] ^[2] ^[3] . They are based on the Fast Fourier Transform (FFT, Fast Fourier Transform , FFT ) and use the algorithm. The cryptographic strength of SWIFFT (in the asymptotic sense) ^{[4] is} mathematically proven using the recommended parameters ^[5] . Finding collisions in SWIFFT in the worst case requires no less time than finding short vectors in cyclic / . Practical application of SWIFFT will be valuable precisely in those cases when resistance to collisions is especially important. For example, digital signatures that must remain reliable for a long time.

This algorithm provides a bandwidth of about 40 Mb / s on an Intel Pentium 4 processor with a clock frequency of 3.2 GHz ^[6] ^[1] . A study was conducted aimed at accelerating the FFT, which is used in SWIFFT ^[7] . As a result, the speed of the algorithm could be increased by more than 13 times ^[6] . This SWIFFT implementation turned out to be faster than the implementation of widespread hash functions ^[8] .

At the competition of the US National Institute of Standards and Technology ^{[2] in} 2012, SWIFFTX (SWIFFT modification) was proposed as SHA-3 (to replace older SHA-2 and especially SHA-1 ^[9] ), but was rejected in the first round ^{[ 10]} .

Job Description

SWIFFT functions can be described as a simple algebraic expression over some polynomial ring $R$ ${\ displaystyle R}$ $R$ ^[1] ^[11] . The family of functions depends on three main parameters.: let $n$ ${\ displaystyle n}$ $n$ will be a power of 2, $m>0$ ${\ displaystyle m> 0}$ $m>0$ Is a small integer, and $p>0$ ${\ displaystyle p> 0}$ $p>0$ - Not necessarily a prime , but it’s best to choose it as a prime. Define $R$ ${\ displaystyle R}$ $R$ like a kind ring $R=\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ ${\ displaystyle R = \ mathbb {Z} _ {p} [\ alpha] / (\ alpha ^ {n} +1)}$ $R=\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ . For example, the ring of polynomials in $\alpha$ ${\ displaystyle \ alpha}$ $\alpha$ whose coefficients are integers, $p$ ${\ displaystyle p}$ $p$ - the number by which we perform the division modulo, and $\alpha ^{n}+1$ ${\ displaystyle \ alpha ^ {n} +1}$ $\alpha ^{n}+1$ . Item from $R$ ${\ displaystyle R}$ $R$ may be a polynomial of degree less $n$ ${\ displaystyle n}$ $n$ with coefficients from $Z_{p}$ ${\ displaystyle Z_ {p}}$ $Z_{p}$ .

A specific function in the SWIFFT family is defined as $m$ ${\ displaystyle m}$ $m$ fixed items $a_{1},\ldots ,a_{m}\in R$ ${\ displaystyle a_ {1}, \ ldots, a_ {m} \ in R}$ $a_{1},\ldots ,a_{m}\in R$ rings $R$ ${\ displaystyle R}$ $R$ called multipliers. This function over the ring $R$ ${\ displaystyle R}$ $R$ can be written as follows:

$\sum _{i=1}^{m}(a_{i}\cdot x_{i})$ ${\ displaystyle \ sum _ {i = 1} ^ {m} (a_ {i} \ cdot x_ {i})}$ $\sum _{i=1}^{m}(a_{i}\cdot x_{i})$ ,

Where $x_{1},\ldots ,x_{m}\in R$ ${\ displaystyle x_ {1}, \ ldots, x_ {m} \ in R}$ - polynomials with binary coefficients corresponding to a binary input message of length $m n$ ${\ displaystyle mn}$ .

The operation algorithm is as follows: ^[1] ^[12] ^[11]

Is taken $\alpha$ ${\ displaystyle \ alpha}$ - irreducible polynomial over $\mathbb {Z} [\alpha ]$ ${\ displaystyle \ mathbb {Z} [\ alpha]}$
A message is input $M$ ${\ displaystyle M}$ lengths $m n$ ${\ displaystyle mn}$
$M$ ${\ displaystyle M}$ converted to a set of $m$ ${\ displaystyle m}$ polynomials $p_{i}$ ${\ displaystyle p_ {i}}$ in a certain ring of polynomials $R$ ${\ displaystyle R}$ with binary coefficients
Fourier coefficients are calculated for each $p_{i}$ ${\ displaystyle p_ {i}}$
Fixed Fourier coefficients are set. $a_{i}$ ${\ displaystyle a_ {i}}$ depending on the SWIFFT family
Fourier coefficients are multiplied in pairs $p_{i}$ ${\ displaystyle p_ {i}}$ with $a_{i}$ ${\ displaystyle a_ {i}}$ for each $i$ ${\ displaystyle i}$
The inverse Fourier transform is used in order to obtain $m$ ${\ displaystyle m}$ polynomials $f_{i}$ ${\ displaystyle f_ {i}}$ degrees no more $2n$ ${\ displaystyle 2n}$
Calculated $f=\sum _{i=1}^{m}(f_{i})$ ${\ displaystyle f = \ sum _ {i = 1} ^ {m} (f_ {i})}$ modulo $p$ ${\ displaystyle p}$ and $\alpha ^{n}+1$ ${\ displaystyle \ alpha ^ {n} +1}$ .
$f$ ${\ displaystyle f}$ converted to $n\log(p)$ ${\ displaystyle n \ log (p)}$ bits and send them to the output

The fast Fourier transform operation in step 4 is easy to reverse. It is carried out in order to achieve mixing - mixing bits supplied to the input.
The linear combination in step 6 leads to , because it compresses the input.

Example

The specific values for the parameters n , m and p are selected as follows: n = 64, m = 16, p = 257 ^[13] . For these parameters, any fixed compression function of the family will accept a message of length mn = 1024 bits (128 bytes) as input. The output is in the range $\mathbb {Z} _{p}^{n}$ ${\ displaystyle \ mathbb {Z} _ {p} ^ {n}}$ which has a size $p^{n}=257^{64}$ ${\ displaystyle p ^ {n} = 257 ^ {64}}$ . Output in $\mathbb {Z} _{p}^{n}$ ${\ displaystyle \ mathbb {Z} _ {p} ^ {n}}$ can be represented using 528 bits (66 bytes).

Calculation of the result of multiplication of polynomials

The hardest part to calculate the above expression is to calculate the result of the multiplication $a_{i}\cdot x_{i}$ ${\ displaystyle a_ {i} \ cdot x_ {i}}$ ^[1] ^[14] . A quick way to compute this product is to use , which states that under certain conditions the following holds:

{\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}

{\ displaystyle {\ mathcal {F}} \ {f * g \} = {\ mathcal {F}} \ {f \} \ cdot {\ mathcal {F}} \ {g \}}

Here ${\mathcal {F}}$ ${\ displaystyle {\ mathcal {F}}}$ denotes the Fourier transform , and the operation $\cdot$ ${\ displaystyle \ cdot}$ means multiplying coefficients with the same index. In the general case of convolution theorems $*$ ${\ displaystyle *}$ convolution matters, not multiplication. However, it can be shown that multiplication of polynomials is a convolution.

Fast Fourier Transform

To find the Fourier transform, we use the Fast Fourier Transform (FFT), which is performed in $O(n\log(n))$ ${\ displaystyle O (n \ log (n))}$ ^[1] . The multiplication algorithm is as follows ^[14] : we calculate all the Fourier coefficients for all polynomials immediately using the FFT. Then we multiply the corresponding Fourier coefficients of two polynomials in pairs. After that we use the inverse FFT, after which we get a polynomial of degree not higher $2n$ ${\ displaystyle 2n}$ .

Discrete Fourier Transform

Instead of the usual Fourier transform in SWIFFT, the discrete Fourier transform (DFT) ^[1] ^{[14] is used} . It uses the roots of unity in $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ instead of complex roots from one. This will be true if $\mathbb {Z} _{p}$ ${\ displaystyle \ mathbb {Z} _ {p}}$ Is a finite field , and its 2 n ^th simple roots of unity exist in this field. These conditions will be satisfied if we take such a prime $p$ ${\ displaystyle p}$ , what $p-1$ ${\ displaystyle p-1}$ divided by $2n$ ${\ displaystyle 2n}$ .

Select options

The parameters m , p , n must satisfy the following requirements ^[15] :

n must be a power of two
p must be a prime
p -1 should be divided by 2 n
$\log(p)<$ ${\ displaystyle \ log (p) <}$ m

You can take, for example, the following parameters: n = 64, m = 16, p = 257. We take bandwidth at the level of 40Mb / s ^[6] , protection from collision search - $2^{106}$ ${\ displaystyle 2 ^ {106}}$ operations.

Statistical Properties

Universal hashing. The SWIFFT family of functions is universal ^[1] . In other words, for any different fixed $x,x*$ ${\ displaystyle x, x *}$ and a randomly selected function $f$ ${\ displaystyle f}$ from the family the probability that the equality holds $f(x)=f(x*)$ ${\ displaystyle f (x) = f (x *)}$ , is inversely proportional to the size of the selected range.
Regularity. Functions from the SWIFFT family of compression functions are regular ^[1] .
Entropy generator. SWIFFT is ^[1] . For hash tables and the applications associated with them, it is desirable that the keys for the values supplied to the function be distributed evenly (or close to uniform distribution), even if the input values are not evenly distributed. Hash functions that behave in a similar way are called entropy generators, because they can represent unevenly distributed parameters that are (almost) uniform in output. Formally, this property usually has a family of functions from which one function was randomly selected.

Cryptographic Properties and Security

SWIFFT is not a due to linearity ^[1] . For an arbitrary function $f$ ${\ displaystyle f}$ from the SWIFFT family the following is true: for two input parameters $x_{1}$ ${\ displaystyle x_ {1}}$ , $x_{2}$ ${\ displaystyle x_ {2}}$ such that $x_{1}+x_{2}$ ${\ displaystyle x_ {1} + x_ {2}}$ can also be an input parameter, executed $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ ${\ displaystyle f (x_ {1}) + f (x_ {2}) = f (x_ {1} + x_ {2})}$ . The fulfillment of this ratio does not fit a random function, and an attacker can easily distinguish our function from a random one.

The cryptographic resistance to collisions (in the asymptotic sense) is proved for the SWIFFT family of functions under the relatively moderate assumption that the problem of finding short vectors in cyclic / ideal lattices is difficult in the worst case. This means that the SWIFFT family of functions is also resistant to the attack of finding the second prototype ^[4] ^[16] .

Theoretical Strength

SWIFFT - ^[1] ^[3] . As in most cases, the proof of the stability of functions is based on the fact that the mathematical problem used in functions cannot be solved in polynomial time. This means that the stability of SWIFFT lies only in the fact that it is based on a complex mathematical problem.

In the case of SWIFFT, the proven stability lies in the problem of finding short vectors in cyclic / ^[17] . It can be proved that the following statement is true: suppose we have an algorithm that can find collisions of a function $f$ ${\ displaystyle f}$ for a random version of SWIFFT obtained from $f$ ${\ displaystyle f}$ for some possible time $T$ ${\ displaystyle T}$ with probability $p$ ${\ displaystyle p}$ . This means that the algorithm works only on a small but noticeable proportion of the functions of the family. Then we can also find the algorithm $f_{2}$ ${\ displaystyle f_ {2}}$ who can always find a short vector on any ideal lattice above the ring $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ ${\ displaystyle \ mathbb {Z} _ {p} [\ alpha] / (\ alpha ^ {n} +1)}$ for some time possible $T_{2}$ ${\ displaystyle T_ {2}}$ dependent on $T$ ${\ displaystyle T}$ and $p$ ${\ displaystyle p}$ . This means that finding collisions in SWIFFT is no less difficult, the task of finding short vectors in a lattice over $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ ${\ displaystyle \ mathbb {Z} _ {p} [\ alpha] / (\ alpha ^ {n} +1)}$ , for the solution of which there are only exponential algorithms.

Practical Resilience

The authors of this hash function examined it for vulnerabilities to various attacks and found that the “birthday” attack requires the least amount of hash counting ( ^2,106 ) to find collisions. ^[18] ^[1] . Permutation attacks require ^2,448 counting operations for standard parameters. A complete enumeration of possible values will require ^2,528 hash counting operations. This, as a rule, is enough to make an enemy attack impossible.

Notes

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ Lyubashevsky et al., 2008 .
↑ ¹ ² Arbitman et al., 2008 .
↑ ¹ ² Györfi et al., 2012 , p. 2.
↑ ¹ ² Arbitman et al., 2008 , p. one.
↑ Buchmann, Lindner, 2009 , p. 1-2.
↑ ¹ ² ³ Györfi et al., 2012 , p. 15.
↑ Györfi et al., 2012 , p. 15-16.
↑ Györfi et al., 2012 , p. sixteen.
↑ PRE- SHA-3 COMPETITION (unopened) . National Institute of Standards and Technology (April 15, 2005).
↑ Second Round Candidates (Neopr.) . National Institute of Standards and Technology (January 19, 2010). Date of treatment February 14, 2010.
↑ ¹ ² Györfi et al., 2012 , p. 3.
↑ Arbitman et al., 2008 , p. 4-5.
↑ Györfi et al., 2012 .
↑ ¹ ² ³ Györfi et al., 2012 , p. four.
↑ Buchmann, Lindner, 2009 .
↑ Šarinay, 2010 , p. 9.
↑ Arbitman et al., 2008 , p. 10-11.
↑ Buchmann, Lindner, 2009 , p. 2.

Literature

Books

Schneier B. Applied Cryptography. Protocols, algorithms, C source code = Applied Cryptography. Protocols, Algorithms and Source Code in C. - M .: Triumph, 2002 .-- 816 p. - 3000 copies. - ISBN 5-89392-055-4 .

Articles

Lyubashevsky V. , Micciancio D. , Peikert C. et al. SWIFFT: A Modest Proposal for FFT Hashing // Fast Software Encryption - 2008. - Vol. 5086. - P. 54–72. - doi: 10.1007 / 978-3-540-71039-4_4
<a href=" https://wikidata.org/wiki/Track:Q5436988 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21681005 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21681006 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21681000 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21681003 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21681002 "> </a>
Arbitman Y. , Dogon G. , Lyubashevsky V. et al. SWIFFTX: A Proposal for the SHA-3 Standard - 2008.
<a href=" https://wikidata.org/wiki/Track:Q21682527 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21682526 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21681003 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21681002 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21682529 "> </a>
Buchmann J. , Lindner R. Secure Parameters for SWIFFT // Progress in Cryptology - INDOCRYPT 2009 : 10th International Conference on Cryptology in India, New Delhi, India, December 13-16, 2009. Proceedings / B. Roy , N. Sendrier - Springer Berlin Heidelberg , 2009. - P. 1-17. - ISBN 978-3-642-10627-9 - doi: 10.1007 / 978-3-642-10628-6_1
<a href=" https://wikidata.org/wiki/Track:Q1697321 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21740532 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21740521 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21587985 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21740526 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21740529 "> </a> <a href = " https : //wikidata.org/wiki/Track: Q21740534 "> </a>
Šarinay J. Interpreting Hash Function Security Proofs // Provable Security : 4th International Conference, ProvSec 2010, Malacca, Malaysia, October 13-15, 2010. Proceedings / S. Heng , K. Kurosawa - Springer Berlin Heidelberg , 2010. - P. 119-132. - ISBN 978-3-642-16279-4 - doi: 10.1007 / 978-3-642-16280-0_8
<a href=" https://wikidata.org/wiki/Track:Q21740559 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21587985 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21740565 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21740570 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21740568 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21740562 "> </a>
Győrfi T. , Cret O. , Hanrot G. et al. High-Throughput Hardware Architecture for the SWIFFT / SWIFFTX Hash Functions // Cryptology ePrint Archive - International Association for Cryptologic Research , 2012.
<a href=" https://wikidata.org/wiki/Track:Q21682545 "> </a> <a href=" https://wikidata.org/wiki/Track:Q5190977 "> </a> <a href = " https://wikidata.org/wiki/Track:Q462005 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21682542 "> </a> <a href = " https://wikidata.org/wiki/Track:Q21682547 "> </a> <a href=" https://wikidata.org/wiki/Track:Q21682548 "> </a> <a href = " https : //wikidata.org/wiki/Track: Q21682544 "> </a>

[_18f339e78149cb51-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ Lyubashevsky et al., 2008 .

[_85b04dd54afd1c97-2] ¹ ² Arbitman et al., 2008 .

[_7bc7c3fd9c34a9c8-3] ¹ ² Györfi et al., 2012 , p. 2.

[_27b0d86e6c1794a4-4] ¹ ² Arbitman et al., 2008 , p. one.

[_734f6af76645363a-5] Buchmann, Lindner, 2009 , p. 1-2.

[_891bd2f06d7c83c4-6] ¹ ² ³ Györfi et al., 2012 , p. 15.

[_3983c9a4a30137f0-7] Györfi et al., 2012 , p. 15-16.

[_891bd2f06d7c83c7-8] Györfi et al., 2012 , p. sixteen.

[9] PRE- SHA-3 COMPETITION (unopened) . National Institute of Standards and Technology (April 15, 2005).

[10] Second Round Candidates (Neopr.) . National Institute of Standards and Technology (January 19, 2010). Date of treatment February 14, 2010.

[_7bc7c3fd9c34a9c9-11] ¹ ² Györfi et al., 2012 , p. 3.

[_ff34bcb761d3d9ef-12] Arbitman et al., 2008 , p. 4-5.

[_c109c587f0782d1e-13] Györfi et al., 2012 .

[_7bc7c3fd9c34a9ce-14] ¹ ² ³ Györfi et al., 2012 , p. four.

[_552562caebed4d62-15] Buchmann, Lindner, 2009 .

[_ccd82bda00acfed0-16] Šarinay, 2010 , p. 9.

[_f3f0ecdd1a62a4af-17] Arbitman et al., 2008 , p. 10-11.

[_9bd440cee43a7db4-18] Buchmann, Lindner, 2009 , p. 2.