はじめに

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のことです。

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)$）

$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が成り立つ

$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も解けるけど逆が成り立つかは未解決っぽいです（自分の調べた範囲では）。