SWIFFT

暗号において、 SWIFFT は、証明可能に安全な ハッシュ関数の集合です。これは、高速フーリエ変換（FFT）の概念に基づいています。 SWIFFTは、FFTに基づいた最初のハッシュ関数ではありませんが、セキュリティの数学的証明を提供することによって、それ自体を分離しています。また、 LLL基底削減アルゴリズムを使用します。 SWIFFTの衝突を発見することは、少なくとも最悪の場合にサイクリック/ [理想格子暗号|理想格子]で短いベクトルを見つけることと同じくらい難しいことが分かります。 SWIFFTは、困難な数学的問題の最悪のシナリオに対してセキュリティを削減することで、他のほとんどの[安全性の高い暗号ハッシュ関数|暗号ハッシュ関数]よりもはるかに強力なセキュリティ保証を提供します。

他の多くの証明された安全なハッシュ関数とは異なり、アルゴリズムは非常に高速で、3.2＆nbsp; GHz Intel Pentium 4で40MB / sのスループットを実現します。SWIFFTは多くの望ましい暗号と統計のプロパティを満たしていますが、 -purpose "暗号化ハッシュ関数。例えば、それは[[疑似乱数関数]ではなく、ランダムなオラクルの適切なインスタンス化ではありません。アルゴリズムは、衝突耐性の証明を与えないほとんどの伝統的なハッシュ関数よりも効率が悪い。したがって、その実用性は、長い間信用できるデジタル署名のような、衝突耐性の証明が特に価値のあるアプリケーションに主にあるでしょう。

[[SWIFFTX]と呼ばれるSWIFFTの修正は、[NISTハッシュ関数競技会]へのSHA-3機能の候補として提案され、第1回で却下された。

アルゴリズム

アルゴリズムは次のとおりです。 ＃[多項式]変数を＆lt;数学＆gt; \ alpha＆lt; / math＆gt;と呼ぶことができます。 ＃ '入力' ：メッセージ＆lt;数学＆gt; M＆lt; / math＆gt;長さ| mn | mn | / mathの長さ

1. Convert <Math> M </ math> <math> m </ math>の集合に、多項式p_i＆lt; / math＆gt;ある多項式環において、R math＆gt;バイナリ係数を持つ。

＃それぞれの<math> p_i </ math>のフーリエ係数を計算する。 SWIFFTを使用します。 ＃<math> a_i </ math>のフーリエ係数を定義して、それらが固定され、SWIFFTのファミリーに依存するようにする。 ＃点ごとにフーリエ係数を乗算する。ここで、p_i </ math>フーリエ係数をa_i </ math>とすると、それぞれの<iath> i </ math>に対して、 ＃逆FFTを使用して、＆lt; math＆gt; m＆lt; / math＆gt;多項式f_i＆lt; / math＆gt;次数<2n </ math>である。

1. Compute <math> f = \ sum_ {i = 1} ^ m（f_i）＆lt; / math＆gt;モジュロ＆lt;数学＆gt; p＆lt;数学＆gt; ＆lt; math＆gt; \ alpha ^ n + 1＆lt; / math＆gt;
2. Convert＆lt; math＆gt; f＆lt; / math＆gt;ここで、nは整数であり、nは整数である。ビットと '出力' 'それです。

• 手順4の FFT操作は反転が容易で、[混同拡散|拡散]を実現する、つまり入力ビットを混合するために実行されます。
• 手順6の線形結合は入力を圧縮するので、混乱を実現します。
• これは、アルゴリズムが何を行うかについての高度な説明です。最終的に高性能アルゴリズムを生成するために、いくつかの高度な最適化が使用されています。

例

'n' '= 64、' m = 16、 'p' '=' 'これらのパラメータの場合、ファミリ内の固定圧縮関数は、長さ「mn」= 1024ビット（128バイト）のバイナリ入力を範囲<math> \ mathbb {Z} ^ n_p＆lt; / math＆gt;は、サイズ<math> p ^ n = 257 ^ {64} ^ math。 ＆lt; math＆gt; \ mathbb {Z} ^ n_p＆lt; / math＆gt; 528ビット（66バイト）を使用して容易に表現することができる。

代数的記述

SWIFFT関数は、いくつかの多項式環 [数学] R / math上の単純な代数表現として記述することができる。これらの関数の族は、3つの主なパラメータ、すなわち、【数1】となる。 2のべき乗であるとすると、<math> m> 0 </ math>小さい整数であり、かつ、<math> p> 0 </ math>モジュラス（必ずしも[プライム]ではありませんが、プライムを選択すると便利です）。 <math> R </ math>を定義する。式（1）の多項式の環は次のようになる。【数1】【数2】【数3】【数4】【数5】【数6】【数7】【数8】【数8】は、 / math＆gt;モジュロ＆lt; math＆gt; p＆lt; math＆gt; ＆lt; math＆gt; \ alpha ^ n + 1＆lt; / math＆gt; <数学> R mathの要素は、次の次数の多項式として書くことができる。 n </ math> Z_p </ math>の係数を有する。 SWIFFTファミリ内の特定の関数は、<math> m </ math>によって指定される。 R mathの固定要素<aath、a ldots、a_m>は、 R 1、...、R nのうちの1つを乗算器と呼ぶ。この関数は、リング "R"上の次の式に対応します。

<数学> \ sum_ {i = 1} ^ m（a_i \ cdot x_i）＆lt; / math＆gt;

R math＆gt;＆lt; math＆gt;の＆lt; math＆gt; x_1、\ ldots、x_m \は、バイナリ係数を有する多項式であり、長さ<math> mn </ math>のバイナリ入力に対応する。

多項式積の計算

上記の式を計算するために、主な問題は、多項式積を計算することである。 a_i \ cdot x_i </ math>。これらの製品を高速に計算する方法は、畳み込み定理によって与えられます。これは、特定の制限の下では、 mathcal {F} \ {f * g \} = \ mathcal {F} \ {f \} \ cdot \ mathcal {F} \ {g \}＆lt; / math＆gt; ここで、＆lt; math＆gt; \ mathcal {F}＆lt; / math＆gt;は、フーリエ変換および<math> \ cdot </ math>を示している。点状の生成物を示す。畳み込み定理の一般的な場合においては、以下のようになる。乗算を表すのではなく畳み込み。しかし、多項式の乗算は畳み込みであることがわかります。

高速フーリエ変換

フーリエ変換を見つけるために、我々は、FFT（[[高速フーリエ変換]）を使用して、その変換を＆lt; math＆gt; O（n \ log（n））</ math>時間である。乗算アルゴリズムは次のようになります。 各多項式の[フーリエ係数]を（一度に）計算するためにFFTを使用します。次に、2つの多項式のそれぞれのフーリエ係数をポイントワイズに乗算し、最後に逆FFTを使用して次数の多項式を返す。 2nπ/ math。

数論的変換

通常のフーリエ変換の代わりに、SWIFFTは数論変換を使用します。数論的変換は、<math> \ mathbb {Z} _p </ math>で1のルーツを使用します。団結の複雑なルーツの代わりに。この作業を行うには、＆lt; math＆gt; \ mathbb {Z} _p＆lt; / math＆gt;は、有限体であり、そのプリミティブ2 n ^{th </ sup>この分野には統一のルーツが存在する。これは、<math> p </ math>とすることによって行うことができる。ここで、mは2以上の整数である。は、＆lt; math＆gt; p-1＆lt; / math＆gt;を除算する。}

パラメータの選択

パラメータ m 、 'には、次の制限があります。

• n は2のべき乗でなければなりません
• p は素数でなければなりません
• p - 1は2の2n の倍数でなければなりません
• log（p）＆lt; / math＆gt; "m"より大きい必要があります（そうでない場合、出力は入力より小さくなりません）

可能な選択肢は '= 64、' '= 16、' '= 257です。約40MB / sのスループットと、約2 ^ {106} 1/2のセキュリティが得られる。衝突を発見するための操作、および512ビットのダイジェストサイズを含む。

統計的プロパティ

• '（ユニバーサルハッシング）' SWIFFTファミリーのファミリーはユニバーサルです。これは、任意の固定された別個の＆lt; math＆gt; x、x '＆lt; / math＆gt;に対して、（xからの） ）= f（x '）・math＆gt;範囲の大きさの逆数です。
• （規則性）。 '圧縮機能のSWIFFTファミリは規則的です。 A関数f math＆gt;＆apos;＆apos;入力x <math>について、正規化されていると言われる。ドメインからランダムに一様に選択された出力f（x）その範囲にわたって均一に分布している。
• '（ランダム性抽出器）' SWIFFTは[ランダム性抽出器]です。ハッシュテーブルおよび関連するアプリケーションでは、入力が一様でなくても、ハッシュ関数の出力を均一に（または可能な限り一様に）分布させることが通常望ましい。そのような保証を与えるハッシュ関数は、（ほぼ）一様分布出力への入力の不均一なランダム性を「蒸留」するため、randomness extractorとして知られています。正式には、ランダム抽出は実際には関数のファミリのプロパティであり、そこからランダムに1つの関数が選択されます（入力には無視されます）。

暗号のプロパティとセキュリティ

• SWIFFTは線形性のため、擬似乱ではありません。任意の関数に対して、f </ math>は、 x_1 </ math>、<math> x_2 </ math>のいずれかの2つの入力から、 x_1 + x_2 </ math>となるように、が有効な入力であるとすると、それは、f（x_1）+ f（x_2）= f（x_1 + x_2）</ math>である。この関係は、ランダムな関数では非常に起こりにくいので、敵対者は私たちの関数をランダムな関数と簡単に区別することができます。
• SWIFFT関数はランダムなオラクルのように振る舞うことは、著者らによって主張されていません。関数は、本当にランダムな関数のように動作する場合、ランダムなオラクルのように振舞うと言われています。これは、関数が固定され公開されている点で擬似乱数とは異なります。
• SWIFFTファミリは、最悪の場合循環的に短いベクトルを見つけるのが難しいという比較的軽度の仮定の下で、証明可能衝突耐性（漸近的な意味で） /理想格子。これは、家族が第二のプリイメージ耐性でもあることを意味する。

理論的なセキュリティ

SWIFFTは証明された安全な暗号化ハッシュ関数の一例です。ほとんどのセキュリティ証明と同様に、SWIFFTのセキュリティ証明は、削減を使用して、数学的問題を解決するのが難しい特定のものに依存しています。これは、SWIFFTのセキュリティがこの数学的問題の難しさに強く依存していることに注意してください。

SWIFFTの場合の削減は、サイクリック/ 理想格子において短いベクトルを見つける問題である。次のことが証明されます： ここで、<math> f </ math>によって与えられるSWIFFTのランダムバージョンに対して、 ＆lt; math＆gt; f＆lt; / math＆gt;で衝突を見つけることができます。実現可能な時間内に確率τmと確率τmとの間で計算される。このアルゴリズムはSWIFFTファミリーのごく一部でしか動作しません。次に、アルゴリズム<math> f_2 </ math>を見つけることができる。これはリング上の「任意の」理想格子内の短いベクトルを常に見つけることができる（数式1）。可能な時間においては、T 1 / T 1に依存して、いくつかの実行可能な時間T 2 / <math> p </ math>。 これは、SWIFFTにおける衝突を発見することは、少なくとも格子上の短いベクトルを見つける最悪のシナリオと同じくらい難しいことを意味する。 ; / math＆gt;。現時点では、ショートベクトルを見つけるための最も速いアルゴリズムは、すべてにおいて指数関数的である。これにより、SWIFFTのセキュリティが弱い「弱いインスタンス」の重要なセットが存在しないことが保証されます。この保証は、他の証明可能な安全なハッシュ関数によっては与えられていません。

実用的なセキュリティ

動作中の攻撃としては、一般化されたバースデー攻撃があり、これは2＆quot; 106＆lt;＆lt; 2 448を取る「反転攻撃（inversion attack）」と呼ばれる。標準的なパラメータ選択のための操作。これは通常、敵が実行不可能な攻撃を行うのに十分であると考えられます。

ソース

http://wikipedia.org/