QUAD（暗号）

暗号化において、QUAD暗号は証明可能なセキュリティの議論を念頭に置いて設計された ストリーム暗号です。

QUAD は、有限体 GF(q) 上の n 個の未知数を持つ m=kn 方程式のランダムに選択された多変量二次方程式システム S=(Q ₁、...、Q _m ) の反復に依存します。キーストリーム生成プロセスは、各反復で (k -1) n GF(q) キーストリーム値を生成するために、次の 3 つの手順を反復するだけです。

• GF(q)値のkn組S(x) = (Q ₁ (x),..., Q _kn (x))を計算します。ここで、xは内部状態の現在の値です。
• (k-1)n GF(q)キーストリーム値のシーケンス(Q _n+1 (x),..., Q _{kn (x))を出力する}
• 内部状態xをn個のGF(q)の最初の生成値のシーケンス（Q ₁ (x),..., Q _n (x)）で更新します。

QUAD は最新のストリーム暗号です。つまり、キーと初期化値 (IV) を使用してキーストリーム シーケンスを生成します。多変量二次方程式に依存するキーと IV の設定も定義されています。

QUAD のキーストリーム生成のセキュリティは、MQ 問題の推測される難解性、つまり多変量二次方程式を解くことに帰着することが証明できます。最初の証明は、旧式のストリーム暗号 (キーが初期状態) のフィールド GF(2) 上で行われました。これは後に Berbain と Gilbert によって拡張され、最新の暗号のセットアップ手順 (キーから初期状態を導出するセットアップ段階を含む) が考慮されました。疑似ランダム関数としての暗号全体のセキュリティは、MQ 問題の推測される難解性と関連している可能性があります。著者らは、古典的な攻撃に対する暗号の耐性も研究しました。

著者らは、80ビットのキー、80ビットのIV、n = 160ビットの内部状態を持つQUADのバージョンを使用することを推奨しています。これは、240^ビットのキーストリームが生成されるまで、各反復で160ビットのキーストリーム（m = 320）を出力します。^[1]

Eurocrypt 2006 では、GF(2)、GF(16)、GF(256) の各フィールド上の 160 ビットの状態と出力ブロックを持つ QUAD インスタンスの速度レポートが発表されました。これらの速度レポートは、SAC 2006 で Berbain、Billet、Gilbert が発表した「多変量二次システムの効率的な実装」の分析の一部でした。^[2] この分析 (QUAD ストリーム暗号だけでなく、いくつかの多変量公開鍵方式も対象) では、セキュリティの側面を考慮せずに、フィールドのサイズを変更することによるパフォーマンスへの影響を部分的に調査しました。^[2]

QUAD の初期のセキュリティ定理は、体 GF(2) に対してのみ有効であり、推奨パラメータはセキュリティの証明と矛盾しません。セキュリティ定理を提示した QUAD の著者は、Eurocrypt 2006 でこの方式を提案したときに、提案パラメータでの QUAD の破綻がセキュリティ証明定理と矛盾しないことを認めました。しかし、著者は、約 2 ^{80の望ましい}セキュリティ レベルを提供するのに十分であると考えていたようです。

Yang、Chen、Bernstein、Chenは、さまざまなパラメータセットのセキュリティを研究し、そのうちのいくつかは非常に安全ではないことを発見しました。^[3]彼らの論文では、QUADへの攻撃と根本的な難問への攻撃の理論的および実践的側面の両方について説明しています。たとえば、この論文では、XL-Wiedemannを使用してGF(256)インスタンスQUAD (256, 20, 20)を約2 ⁶⁶ Opteronサイクルで破り、根本的な難問を約2 ⁴⁵サイクルで破る方法を示しており、これは成功しています。ただし、この論文によると、 XL-Wiedemannを使用してQUADの著者が推奨するQUAD(2,160,160)バージョンのインスタンスを解決するには 約2 ¹¹⁰かかります。

Yangらによる研究では、セキュリティ定理はしばしば緩い係数による縮小に依存しているという事実が強調されており、これを考慮すると、提案されたバージョンのパラメータセットはどれもセキュリティの証明には不十分です。証明可能なセキュリティの例はQUAD(2,320,320)であり、これは当初提案されたものの2倍の幅です。^[3]

GF(q)に対してもセキュリティ定理が証明できるが、より大きなルーズネス係数が必要である。これと、より効率的な実装のためのQUADの拡張はLiuらによって提案されている^{[4] 。}

• Côme Berbain、Henri Gilbert。IV 依存ストリーム暗号のセキュリティについて(PDF)。2007 年高速ソフトウェア暗号化に関する国際ワークショップ。
• Jean-Philippe Aumasson、Willi Meier。多変量ハッシュ関数の分析(PDF)。第 10 回情報セキュリティおよび暗号学に関する国際会議。