XDHの仮定

XDH_assumption
外部ディフィー・ヘルマン（XDH）仮定がある計算硬度の仮定に使用楕円曲線暗号。XDHの仮定は、暗号化に役立つプロパティを持つ楕円曲線の特定のサブグループが存在することを前提としています。具体的には、XDHは2つの異なるグループの存在を意味します ⟨ 1 、 2 ⟩ { langle { mathbb {G}} _ {1}、{ mathbb {G}} _ {2} rangle}
次のプロパティを使用します。
離散対数問題（DLP）、計算のDiffie-Hellman問題（CDH）、および計算コのDiffie-Hellman問題は、すべての難治性であります 1
{{ mathbb {G}} _ {1}}
と 2
{{ mathbb {G}} _ {2}} 効率的に計算可能な双線形写像（ペアリング）が存在します e （（ ⋅ ⋅ ）。 ： 1
×× 2
{e（ cdot、 cdot）：{ mathbb {G}} _ {1} times { mathbb {G}} _ {2} rightarrow { mathbb {G}} _ {T}} 判断のDiffie-Hellman問題（DDH）は難治性であります 1
{{ mathbb {G}} _ {1}} 上記の定式化は非対称XDHと呼ばれます。仮定のより強力なバージョンは、（対称XDH、又はSXDH場合）を保持DDHがあるにも難治性で 2
{{ mathbb {G}} _ {2}} XDHの仮定は、一部のペアリングベースの暗号化プロトコルで使用されます。特定の楕円曲線サブグループでは、効率的に計算可能な双線形写像（ペアリング）の存在により、DDH問題の実用的な解決策が可能になります。ギャップDiffie-Hellman（GDH）グループと呼ばれるこれらのグループは、3部構成の鍵交換、IDベースの暗号化、秘密のハンドシェイク（いくつか例を挙げます）など、さまざまな新しい暗号化プロトコルを容易にします。ただし、GDHグループ内のDDHの計算の容易さも、暗号システムを構築する際の障害になる可能性がたとえば、GDHグループ内でElGamalなどのDDHベースの暗号システムを使用することはできません。DDH仮定は、XDHグループのペアの少なくとも1つに当てはまるため、これらのグループを使用して、ElGamalスタイルの暗号化やその他の新しい暗号化技術を可能にするペアリングベースのプロトコルを構築できます。
実際には、XDHの仮定は、MNT楕円曲線の特定のサブグループに当てはまると考えられています。この概念は、Scott（2002）によって最初に提案され、その後、署名スキームの効率を改善する手段としてBoneh、Boyen、およびShacham（2002）によって提案されました。この仮定は、Ballard、Green、de Medeiros and Monrose（2005）によって正式に定義され、提案された実装の完全な詳細がその作業で進められました。この仮定の妥当性の証拠は、Verheul（2001）とGalbraith and Rotger（2004）による、効率的に計算可能なペアリングを持つ2つの特定の楕円曲線サブグループに歪みマップが存在しないことの証明です。ペアリングと歪みマップは現在、楕円曲線グループのDDH問題を解決する唯一の既知の手段であるため、DDHの仮定はこれらのサブグループにも当てはまりますが、ペアリングは異なるグループの要素間で実行可能であると考えられます。

参考文献
マイクスコット。シンプルなトークンとPINを使用した認証済みIDベースの交換とリモートログイン。E-printアーカイブ（2002/164）、2002年。（pdfファイル）
ダン・ボウネイ、ザビエル・ボイエン、ホワフ・シャチャム。短いグループ署名。CRYPTO 2004.（pdfファイル）
ルーカスバラード、マシューグリーン、ブレノデメデイロス、ファビアンモンローズ。キーワード検索可能な暗号化による相関耐性のあるストレージ。E-printアーカイブ（2005/417）、2005年。（pdfファイル）
スティーブン・D・ガルブレイス、ビクター・ロジャー。Easy Decision Diffie–Hellmanグループ。LMS Journal of Computation and Mathematics、2004年8月。（）
ER Verheul、XTRが超特異楕円曲線暗号システムよりも安全であるという証拠、B。Pfitzmann（ed。）EUROCRYPT 2001、Springer LNCS 2045（2001）195–210。