スイフト

暗号学において、SWIFFT は証明可能な安全性を持つ ハッシュ関数の集合です。これは高速フーリエ変換(FFT) の概念に基づいています。SWIFFT は FFT に基づく最初のハッシュ関数ではありませんが、安全性の数学的証明を提供することで際立っています。また、LLL 基底削減アルゴリズムも使用します。最悪の場合、 SWIFFTで衝突を見つけることは、巡回格子や理想格子で短いベクトルを見つけることと同じくらい難しいことが示されています。難しい数学的問題の最悪のシナリオに安全性削減を与えることで、SWIFFT は他のほとんどの暗号ハッシュ関数よりもはるかに強力な安全性保証を提供します。

他の多くの証明可能な安全性ハッシュ関数とは異なり、このアルゴリズムは非常に高速で、3.2 GHz Intel Pentium 4 で 40 Mbit/s のスループットを実現します。SWIFFT は多くの望ましい暗号化および統計特性を満たしていますが、「汎用」暗号化ハッシュ関数として設計されたわけではありません。たとえば、これは疑似ランダム関数ではなく、ランダム オラクルの適切なインスタンス化ではありません。このアルゴリズムは、衝突耐性の証明を提供しない従来のハッシュ関数のほとんどよりも効率が低くなります。したがって、このアルゴリズムの実際の使用は、長期間信頼性を維持する必要があるデジタル署名など、衝突耐性の証明が特に重要なアプリケーションで主に行われます。

SWIFFTの改良版であるSWIFFTXがNISTハッシュ関数コンペティション^[1]にSHA-3関数の候補として提案され、第1ラウンドで却下された^{[2] 。}

アルゴリズムは以下のとおりです。^[3]

1. 多項式変数をαと呼ぶことにします。
2. 入力:長さmnのメッセージM
3. M を、バイナリ係数を持つ特定の多項式環R内の多項式p ₁、…、p _mの集合に変換します。
4. SWIFFT を使用して各p _iのフーリエ係数を計算します。
5. a _iのフーリエ係数を固定し、SWIFFT ファミリーに依存するように定義します。
6. 各iについて、フーリエ係数p _iとa _iのフーリエ係数を点ごとに乗算します。
7. 逆 FFT を使用して、次数< 2 nのm 個の多項式f _{i を}取得します。
8. モジュロpとα ⁿ + 1を計算します。${\displaystyle f=\sum _{i=1}^{m}(f_{i})}$
9. fをn log( p )ビットに変換して出力します。

ステップ 4 のFFT演算は簡単に反転でき、拡散、つまり入力ビットの混合を実現するために実行されます。ステップ 6 の線形結合は入力を圧縮するため、混乱を実現します。これはアルゴリズムが行うことの高レベルの説明にすぎず、より高度な最適化がいくつか使用され、最終的に高性能なアルゴリズムが実現されます。

パラメータ( n、m、p )=(64、16、257)と仮定すると、このファミリの固定圧縮関数は、長さmn =1024ビット(128バイト)のバイナリ入力を受け取り、範囲ℤの出力を生成します。^np
_​、サイズはp ⁿ = 257 ⁶⁴です。ℤの出力は^np
_​528 ビット (66 バイト) を使用して簡単に表現できます。

SWIFFT 関数は、ある多項式環 R上の単純な代数式として記述できます。これらの関数の族は、3 つの主なパラメータに依存します。n を2 の累乗、m > 0を小さな整数、p > 0を法 (必ずしも素数である必要はありませんが、素数を選択すると便利です) とします。Rを環 R = ℤ p [α]/(α n + 1) 、つまり p と α n + 1 を法とする整数係数を持つ α の多項式の環として 定義し_ます。R^の元は、ℤ ^pに係数を持つ次数< n_の多項式として記述できます。SWIFFT 族の特定の関数は、環のm個の固定元a ₁、…、a _m ∈ Rによって指定され、これらは乗数と呼ばれます。関数は、 R上の次の式に対応します。 ${\displaystyle R}$

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

x ₁ , …, x m _∈ Rはバイナリ係数を持つ多項式であり、長さmnのバイナリ入力に対応します。

上記の式を計算する際、主な問題は多項式積a _i ⋅ x _iを計算することです。これらの積を素早く計算する方法は、畳み込み定理によって与えられます。これは、特定の制約の下で、F { f ∗ g } = F { f } ⋅ F { g }が成り立つことを意味しています。ここで、F はフーリエ変換を表し、⋅は点ごとの積を表します。畳み込み定理の一般的なケースでは、∗ は乗算ではなく畳み込みを表します。ただし、多項式乗算は畳み込みであることが示されます。

高速フーリエ変換は各多項式のフーリエ係数を求めるために使用され、次にそれらの係数は他の多項式のそれぞれのフーリエ係数と点ごとに乗算されます。次に、結果として得られた係数は逆高速フーリエ変換を使用して 次数2 n未満の多項式に変換されます。

SWIFFT は通常のフーリエ変換の代わりに数論的変換を使用します。数論的変換では、複素数 1 の根の代わりにℤ _pの 1 の根を使用します。これが機能するには、ℤ _{p が}有限体であり、この体に原始2 n^{乗1 の根が存在する必要があります。これは、} 2 n がp − 1 を割り切るようなp を素数としてとることで実行できます。

パラメータm、p、およびnには次の制限が適用されます。

• nは2の累乗でなければならない。
• pは素数でなければならない、
• p − 1 は2 nの倍数でなければならず、
• log( p ) < m (そうでない場合、出力は入力より小さくなりません)。

可能な選択肢は( n , m , p ) = (64,16,257)であり、これにより、約 40 Mbit/s のスループット、衝突を検出するための約2 ^{106 回}の演算のセキュリティ、および 512 ビットのダイジェスト サイズが達成されます。

• ユニバーサルハッシュ。SWIFFT関数ファミリーはユニバーサルです。つまり、任意の固定された異なるxとyに対して、 f ( x ) = f ( y )となる確率 (ファミリーからランダムに選択されたfに対して)は、範囲のサイズの逆数になります。
• 規則性。SWIFFTファミリーの圧縮関数は規則的です。関数fは、ドメインから一様にランダムに選択された入力xに対して、出力f ( x ) が範囲全体に一様に分布している場合に規則的であると言われます。
• ランダム性抽出器。SWIFFTはランダム性抽出器です。ハッシュ テーブルや関連アプリケーションでは、入力が均一でない場合でも、ハッシュ関数の出力が均一に (または可能な限り均一に近い) 分布していることが通常望ましいです。このような保証を与えるハッシュ関数は、入力の非均一ランダム性を (ほぼ) 均一に分布した出力に抽出するため、ランダム性抽出器と呼ばれます。正式には、ランダム性抽出は実際には関数のファミリーの特性であり、その中から 1 つの関数がランダムに (入力を無視して) 選択されます。

• SWIFFT は線形性のため、疑似ランダムではありません。このファミリの任意の関数fと、 x + yも有効な入力である任意の 2 つの入力 x と y については、 f ( x ) + f ( y ) = f ( x + y ) が成り立ちます。この関係はランダム関数に当てはまる可能性は非常に低いため、敵対者は簡単にこの関数をランダム関数と区別できます。
• 著者らは、SWIFFT 関数がランダム オラクルのように動作すると主張しているわけではありません。関数が本当にランダムな関数のように動作する場合、その関数はランダム オラクルのように動作すると言われます。これは、関数が固定され公開されている点で疑似ランダム性とは異なります。
• SWIFFT ファミリは、巡回/理想格子で短いベクトルを見つける最悪のケースの難しさに関する比較的穏やかな仮定の下で、衝突耐性（漸近的な意味で）があることが証明されています。これは、ファミリが第 2 原像耐性でもあることを意味します。

SWIFFT は、証明可能なほど安全な暗号ハッシュ関数の一例です。ほとんどのセキュリティ証明と同様に、SWIFFT のセキュリティ証明は、解決が困難な特定の数学的問題の帰結に依存しています。つまり、SWIFFT のセキュリティはこの数学的問題の難しさに大きく依存していることに注意してください。

SWIFFT の場合の還元は、巡回/理想格子内の短いベクトルを見つける問題への還元です。次のことが成り立つことが証明できます。fで与えられた SWIFFT のランダムバージョンに対して、 f内の衝突をT の実行可能時間内にp の確率で見つけることができるアルゴリズムがあるとします。アルゴリズムが SWIFFT ファミリの小さいが目立つ部分でのみ機能することが許されます。すると、 T と p に依存して、リング ℤ p [α]/(α n + 1) 上の任意の理想格子内の短いベクトルを T 2 の実行可能時間内に常に見つけることができるアルゴリズム f 2 も見つかります。これは、 SWIFFT 内で衝突を見つけることが、 ℤ _p [α]/(α ⁿ + 1)上の格子_内の短いベクトルを見つける_という最悪のシナリオと_同じくらい^難しいことを意味します。現時点では^{[いつ? ]}、短いベクトルを見つけるための最速のアルゴリズムはすべてnに関して指数関数的です。これにより、SWIFFT のセキュリティが弱い「弱いインスタンス」の重要なセットが存在しないことが保証されることに注意してください。この保証は、他のほとんどの証明可能なセキュリティ ハッシュ関数では提供されません。

既知の有効な攻撃としては、2 ^{106 回の演算を必要とする}一般化誕生日攻撃と、標準的なパラメータ選択に2 ^{448 回の演算を必要とする}反転攻撃があります。通常、これは敵対者による攻撃を不可能にするのに十分であると考えられています。