XDH仮定
Computational hardness assumption used in elliptic curve cryptography

外部Diffie-Hellman（XDH）仮定は、楕円曲線暗号において用いられる計算困難性仮定である。XDH仮定は、暗号に有用な特性を持つ楕円曲線の特定の部分群が存在する場合に成立する。具体的には、XDHは以下の特性を持つ 2つの異なる群の存在を意味する。 ⟨ G 1 , G 2 ⟩ {\displaystyle \langle {\mathbb {G} }_{1},{\mathbb {G} }_{2}\rangle }

  1. 離散対数問題(DLP)、計算 Diffie-Hellman 問題(CDH)、および計算 co-Diffie-Hellman 問題はすべて、およびでは解決不可能です。 G 1 {\displaystyle {\mathbb {G} }_{1}} G 2 {\displaystyle {\mathbb {G} }_{2}}
  2. 効率的に計算可能な双線形写像（ペアリング）が存在します。 e ( ⋅ , ⋅ ) : G 1 × G 2 → G T {\displaystyle e(\cdot ,\cdot ):{\mathbb {G} }_{1}\times {\mathbb {G} }_{2}\rightarrow {\mathbb {G} }_{T}}
  3. 決定的Diffie-Hellman 問題(DDH) は、 では解決不可能です。 G 1 {\displaystyle {\mathbb {G} }_{1}}

上記の定式化は非対称XDHと呼ばれます。DDHも において扱いにくい場合、この仮定のより強いバージョン（対称XDH 、またはSXDH）が成立します。 G 2 {\displaystyle {\mathbb {G} }_{2}}

XDH仮定は、いくつかのペアリングベースの暗号プロトコルで使用されています。特定の楕円曲線部分群では、効率的に計算可能な双線形写像（ペアリング）の存在により、 DDH問題の実用的な解決が可能になります。ギャップディフィー・ヘルマン（GDH）群と呼ばれるこれらの群は、三者鍵交換、アイデンティティベース暗号化、秘密ハンドシェイクなど、さまざまな新しい暗号プロトコルを可能にします。ただし、GDH群内でのDDHの計算の容易さは、暗号システムの構築時に障害となることもあります。たとえば、 GDH群内ではElGamalなどのDDHベースの暗号システムを使用することはできません。DDH仮定は少なくとも一方のXDH群のペア内で成り立つため、これらの群を使用して、ElGamalスタイルの暗号化やその他の新しい暗号技術を可能にするペアリングベースのプロトコルを構築できます。

実際には、XDH 仮定は MNT 楕円曲線の特定の部分群で成り立つと考えられています。この概念は、署名方式の効率を改善する手段として、Scott (2002) によって最初に提案され、その後、Boneh、 Boyen および Shacham (2002) によって提案されました。仮定は Ballard、Green、de Medeiros および Monrose (2005) によって正式に定義され、提案された実装の詳細はその研究で詳しく説明されています。この仮定の妥当性の証拠は、効率的に計算可能なペアリングを持つ 2 つの特定の楕円曲線部分群に歪みマップが存在しないという、Verheul (2001) および Galbraith および Rotger (2004) による証明です。ペアリングと歪みマップは現在、楕円曲線群で DDH 問題を解決するための唯一の既知の手段であるため、異なるグループの要素間ではペアリングが依然として可能である限り、これらの部分群で DDH 仮定が成り立つと考えられています。

参考文献

  1. マイク・スコット. 認証IDベースの交換とシンプルなトークンとPINによるリモートログイン. E-print archive (2002/164), 2002. (pdfファイル)
  2. Dan Boneh、Xavier Boyen、Hovav Shacham. ショートグループ署名. CRYPTO 2004. (pdfファイル)
  3. ルーカス・バラード、マシュー・グリーン、ブレノ・デ・メデイロス、ファビアン・モンローズ。キーワード検索可能な暗号化による相関耐性ス​​トレージ。E-printアーカイブ (2005/417)、2005年。(pdfファイル)
  4. スティーブン・D・ガルブレイス、ビクター・ロッガー「Easy Decision Diffie–Hellman Groups」LMS Journal of Computation and Mathematics、2004年8月。（[1] 2005年10月27日、 Wayback Machineにアーカイブ）
  5. ER Verheul、「XTRは超特異楕円曲線暗号よりも安全である証拠」、B. Pfitzmann（編）EUROCRYPT 2001、Springer LNCS 2045（2001）195-210。[2]
Retrieved from "https://en.wikipedia.org/w/index.php?title=XDH_assumption&oldid=1319743253"