はじめに
DH仮定って色々派生系があるので、よく聞くものをまとめておきます。もっと細かい派生もあるのですが際限なくなるのでSDH, XDH, BDHだけ紹介します。
離散対数問題（DLP）は前提としています。DLPは $g, h, p$ が与えられた時に、$g^x \equiv h \pmod{p}$を満たす $x$ を求めるのは計算量的に難しいという問題です。
Diffie–Hellman 仮定の体系図
基本的な系統
| 名称 | 問題設定 | 仮定の強さ |
|---|---|---|
| CDH（Computational DH）仮定 | $g, g^a, g^b$ から $g^{ab}$ を求める | DL ≤ CDH |
| DDH（Decisional DH）仮定 | $g, g^a, g^b, g^c$ から判定：$g^c = g^{ab}$が正しいかを求める | CDH ≤ DDH |
一般にDH仮定って言われたら大体CDHのことです。
Strong DH（SDH）
q-SDHとか記述されることもありますが、同じものを指してます。元論文（Short Signatures Without Random Oracles）では同じ文脈で使ってますね。
入力$ (g, g^x, g^{x^2}, ..., g^{x^q}) $から$(g^{1/(x+c)}, c)$を作るのが困難、つまり「多数のペア」から新しい指数の逆元を作れないという仮定（ただし、$c \in Z^*_p$）
また、ペアリングで使えるようにこれを$G_1, G_2$に拡張すると、
入力$ (g_1, g_2, g_2^x, g_2^{x^2}, ..., g^{x^q}) $から$(g^{1/(x+c)}, c)$を作るのが困難（ただし、$g_1 = \psi(g_2)$）
External DH（XDH）
$G_1 \times G_2 \to G_T$の双線型写像（ただし、$G_1 \to G_2$の準同型写像は存在しない）において以下が定義となっています。
$G_1$でDDHが成り立つ（ただし、$G_2$はDDHでなくても良い）
よく出てくるのは Symmetric XDH（SXDH） で、
$G_1$および$G_2$でDDHが成り立つ
参考: A New Hash-and-Sign Approach and Structure-Preserving Signatures from DLIN
Bilinear DH（BDH）
$G_1, G_2$は位数が素数$q$の群、$\hat{e} : G_1 \times G_1 \to G_2$をAdmissibleな双線型写像とし、$P$を$G_1$の生成元、$a,b,c \in Z_q^*$とした場合に、BDHは以下です。
$(P, aP, bP, cP)$から$\hat{e}(P,P)^{abc}$を計算するのが困難
ちなみにCDHを解ければBDHも解けるけど逆が成り立つかは未解決っぽいです（自分の調べた範囲では）。