多変量暗号

多変数暗号は、有限体上の多変数多項式に基づく非対称暗号 プリミティブの総称です。場合によっては、それらの多項式は基底体と拡大体の両方で定義できます。多項式の次数が2の場合、多変数 二次方程式と呼ばれます。多変数多項式方程式のシステムを解くことは、 NP完全であることが証明されています。^[1] そのため、これらの方式は、多くの場合、ポスト量子暗号の良い候補と見なされています。多変数暗号は、設計と暗号解読の点で非常に生産的でした。全体として、状況は現在より安定しており、最も強力な方式は時の試練に耐えてきました。多変数暗号は、主にポスト量子アルゴリズムの中で最も短い署名を提供するため、署名方式を構築するアプローチとしてより成功したことが判明したことは、一般的に 認められています。 ${\displaystyle F}$

松本勉と今井秀樹(1988) は、 Eurocrypt会議 でいわゆる C* 方式を発表しました。C* はジャック・パタリン (1995) によって破られましたが、松本と今井の一般原理は、改良された提案の世代に影響を与えました。その後の研究で、ジャック・パタリン(フランス語)によって「隠れ単項式暗号システム」が開発されました。これは基底体と拡張体に基づいています。パタリンが 1996 年に開発した「隠れ体方程式」(HFE) は、今日でも人気のある多変数方式です [P96]。HFE のセキュリティは、直接的なグレブナー基底攻撃 [FJ03、GJS06]、キー回復攻撃 (Kipnis & Shamir 1999) [BFP13] などから始まり、徹底的に調査されてきました。HFE のプレーン バージョンは、安全なパラメータが非実用的な方式につながるという意味で、実質的に破られていると考えられています。ただし、マイナス バリアントやビネガー バリアントなどの HFE のいくつかの単純なバリアントを使用すると、すべての既知の攻撃に対して基本的な HFE を強化できます。

HFE に加えて、パタリンは他のスキームも開発しました。1997 年に「バランスのとれたオイルと酢」を発表し、1999 年にはアヴィアド・キプニスとルイ・グービンと共同で「アンバランスなオイルと酢」を発表しました (Kipnis、パタリン、グービン 1999)。

多変数二次方程式には公開鍵と秘密鍵が必要です。秘密鍵は、2 つのアフィン変換 S と T と、簡単に逆変換できる二次写像 で構成されます。アフィン自己準同型の行列を で表し、シフト ベクトルを で表します。 についても同様に表します。言い換えると、 ${\displaystyle P'\colon F^{m}\rightarrow F^{n}}$${\displaystyle n\times n}$ ${\displaystyle S\colon F^{n}\rightarrow F^{n}}$${\displaystyle M_{S}}$${\displaystyle v_{S}\in F^{n}}$${\displaystyle T\colon F^{m}\rightarrow F^{m}}$

• ${\displaystyle S(x)=M_{S}x+v_{S}}$そして
• ${\displaystyle T(y)=M_{T}y+v_{T}}$。

この 3 つのキーは秘密キーであり、トラップドアとも呼ばれます。公開キーは、トラップドアを知らなければ逆変換することが難しいと想定される組み合わせです。 ${\displaystyle (S^{-1},{P'}^{-1},T^{-1})}$${\displaystyle P=S\circ P'\circ T}$

署名は秘密鍵を使用して生成され、公開鍵を使用して次のように検証されます。メッセージは既知のハッシュ関数によってベクトルにハッシュされます。署名は ${\displaystyle y\in F^{n}}$

${\displaystyle x=P^{-1}(y)=T^{-1}\left({P'}^{-1}\left(S^{-1}(y)\right)\right)}$。

署名された文書の受信者は公開鍵 P を所有している必要があります。受信者はハッシュを計算し、署名がを満たしていることを確認します。 ${\displaystyle y}$${\displaystyle x}$${\displaystyle P(x)=y}$

• バランスの悪い油と酢
• 隠れた場の方程式
• NESSIEによるSFLASH
• 虹
• 翻訳
• 石英
• QUAD（暗号）
• 4つの多変量暗号署名方式（GeMMS、LUOV、Rainbow、MQDSS）がNISTポスト量子コンペティションの第2ラウンドに進出しました。レポートのスライド12を参照してください。^[2]

• [BFP13] L. Bettale、 Jean-Charles Faugère、およびL. Perret、「HFE、マルチHFE、および奇数と偶数の特性の変種の暗号解読」。DCC'13
• [FJ03] Jean-Charles Faugèreと A. Joux、「グレブナー基底を用いた隠れ体方程式 (HFE) 暗号システムの代数的暗号解析」。CRYPTO'03
• [GJS06] L. Granboulan、Antoine Joux、J. Stern: HFE の反転は準多項式です。CRYPTO'06。
• Kipnis, Aviad; Shamir, Adi (1999)。「再線形化による HFE 公開鍵暗号システムの暗号解析」。Advances in Cryptology – CRYPTO' 99。ベルリン、ハイデルベルク: Springer。doi : 10.1007 / 3-540-48405-1_2。ISBN 978-3-540-66347-8. ISSN  0302-9743. MR  1729291.
• Kipnis, Aviad; Patarin, Jacques; Goubin , Louis (1999)。「不均衡な油と酢の署名方式」(PDF)。Jacques Stern (編)。暗号学の進歩 - CRYPTO' 99。Eurocrypt'99。Springer。doi : 10.1007 / 3-540-48910- x_15。ISBN 3-540-65889-0. ISSN  0302-9743. MR  1717470.
• 松本 勉、今井 秀樹(1988)。「効率的な署名検証とメッセージ暗号化のための公開二次多項式タプル」。コンピュータサイエンスの講義ノート。ベルリン、ハイデルベルク: シュプリンガー。doi : 10.1007 /3-540-45961-8_39。ISBN 978-3-540-50251-7. ISSN  0302-9743. MR  0994679.
• パタリン、ジャック (1995)。「Eurocrypt'88 の松本と今井の公開鍵方式の暗号解析」。暗号学の進歩 - CRYPT0' 95。コンピュータサイエンスの講義ノート。第 963 巻。ベルリン、ハイデルベルク: シュプリンガー。pp. 248–261。doi : 10.1007/3-540-44750-4_20。ISBN 978-3-540-60221-7. ISSN  0302-9743. MR  1445572.
• [P96] ジャック・パタリン、隠れた体方程式 (HFE) と多項式の同型性 (IP): 2 つの新しい非対称アルゴリズム ファミリ (拡張版)、Eurocrypt '96
• Christopher Wolf およびBart Preneel、多変数二次方程式の問題に基づく公開鍵スキームの分類、現在のバージョン: 2005-12-15
• An Braeken、Christopher Wolf、Bart Preneel、「不均衡な油と酢の署名方式のセキュリティに関する研究」、現在のバージョン: 2005-08-06
• 丁 金台、研究プロジェクト: Rainbow および TTS 多変量公開鍵署名方式の暗号解析
• Jacques Patarin、Nicolas Courtois、Louis Goubin、SFLASH、低コストのスマートカード向けの高速非対称署名方式。基本的な仕様とサポートドキュメント。
• Bo-Yin Yang、Chen-Mou Cheng、Bor-Rong Chen、Jiun-Ming Chen、「低リソース組み込みシステムでの最小化多変量 PKC の実装」、2006 年
• Bo-Yin Yang、Jiun-Ming Chen、Yen-Hung Chen、「TTS: 低コストのスマート カードによる高速署名」、2004 年
• Nicolas T. Courtois、「HFE、Quartz、Sflash などの多変数多項式スキームの短い署名、証明可能セキュリティ、一般的な攻撃、計算セキュリティ」、2005 年
• アルフレッド・J・メネゼス、ポール・C・ヴァン・オーショット、スコット・A・ヴァンストーン共著『応用暗号ハンドブック』、1997年

• [1] HFE公開鍵暗号化と署名
• [2] HFEBoost