XDH仮定

外部Diffie -Hellman (XDH) 仮定は、楕円曲線暗号で使用される計算困難性仮定です。XDH 仮定は、暗号化に有用な特性を持つ楕円曲線の特定のサブグループが存在する場合に成立します。具体的には、XDH は次の特性を持つ 2 つの異なるグループの存在を意味します。 ${\displaystyle \langle {\mathbb {G} }_{1},{\mathbb {G} }_{2}\rangle }$

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

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

XDH 仮定は、ペアリングベースの暗号化プロトコルの一部で使用されています。特定の楕円曲線サブグループでは、効率的に計算可能な双線形写像(ペアリング) の存在により、 DDH問題の実用的な解決が可能になります。ギャップ Diffie–Hellman (GDH) グループと呼ばれるこれらのグループは、三者鍵交換、アイデンティティ ベース暗号化、シークレット ハンドシェイク(ほんの数例) など、さまざまな新しい暗号化プロトコルを可能にします。ただし、GDH グループ内での DDH の計算の容易さは、暗号システムを構築する際の障害にもなります。たとえば、 GDH グループ内でElGamalなどの DDH ベースの暗号システムを使用することはできません。DDH 仮定は少なくとも 1 つの 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 アーカイブ (2002/164)、2002 年。(pdf ファイル)
2. Dan Boneh、Xavier Boyen、Hovav Shacham。ショート グループ署名。CRYPTO 2004。(pdf ファイル)
3. Lucas Ballard、Matthew Green、Breno de Medeiros、Fabian Monrose。キーワード検索可能な暗号化による相関耐性ス​​トレージ。E-print アーカイブ (2005/417)、2005 年。(pdf ファイル)
4. スティーブン・D・ガルブレイス、ビクター・ロッガー。簡単な決定ディフィー・ヘルマン群。LMS計算数学ジャーナル、2004年8月。([1])
5. ER Verheul、「XTRは超特異楕円曲線暗号システムよりも安全である証拠」、B. Pfitzmann (編) EUROCRYPT 2001、Springer LNCS 2045 (2001) 195–210。[2]