多変数暗号
Field of asymmetric cryptographic primitives

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

歴史

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

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

工事

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

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

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

サイン

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

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

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

アプリケーション

参考文献

  1. ^ ガリー、マイケル・R. (1979). 『コンピュータとイントラクタビリティ：NP完全性理論へのガイド』ジョンソン、デイビッド・S. (1945-). サンフランシスコ: WHフリーマン. ISBN 0-7167-1044-7. OCLC  4195125。
  2. ^ Moody, Dustin (2019年8月22日). 「NIST PQC標準化プロセスの第2ラウンド」. NIST . 2020年10月11日閲覧。
  • [BFP13] L. Bettale、 Jean-Charles Faugère、L. Perret、「HFE、Multi-HFE、および奇数と偶数の異形に対する暗号解読」、DCC'13
  • [FJ03] Jean-Charles Faugère、A. Joux、「グレブナー基底を用いた隠れ体方程式（HFE）暗号システムの代数的暗号解析」、CRYPTO'03
  • [GJS06] L. Granboulan、Antoine Joux、J. Stern：「HFEの反転は準多項式である」CRYPTO'06。
  • キプニス、アヴィアド、シャミール、アディ (1999). 「再線形化によるHFE公開鍵暗号システムの暗号解読」.暗号学の進歩 – CRYPTO' 99.ベルリン、ハイデルベルク: シュプリンガー. 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). 「Unbalanced Oil and Vinegar Signature Schemes」（PDF） . Jacques Stern編. Advances in Cryptology – 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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Multivariate_cryptography&oldid=1327291420"