Diffie-Hellman (DH) 鍵共有方式は最新の SSL (TLS) である TLS v1.3 では唯一の鍵共有方式となっているくらい浸透してきた暗号技術かと思います。
皆さん名前ぐらいは聞いたことあるのではないでしょうか？

DH 鍵共有方式の安全性は Diffie-Hellman 仮定というものに基づいているのですが、じつは DH 仮定には Computational Diffie-Hellman (CDH) 仮定と Decisional Diffie-Hellman (DDH) 仮定というふたつのバリエーションが存在します。今日はこれについて語りたいと思います。

おさらい：Diffie-Hellman 鍵共有方式とは？

$G$ を $g$ が生成する位数 $n$ の巡回群 $(G = \langle g \rangle)$ であるとします¹。
伝統的には $G$ は巨大素数 $(p)$ を法とする乗法群 $(G = (\mathbb{Z}/p\mathbb{Z})^\times)$ であったり、最近では楕円曲線群がかなり使われ始めてきています。このとき、Diffie-Hellman 鍵共有方式とは以下のようなプロトコルです。

Alice は $n$ 未満の任意の乱数 $a$ を生成し、$g^a =: A$ を Bob へ送ります。
Bob も同様に $n$ 未満の任意の乱数 $b$ を生成し、$g^b =: B$ を Alice へ送ります。また、$s_{b} := A^b$ を共通の鍵として保管します。
Alice は $s_{a} := B^a$ を共通の鍵として保管します。
$s_{a} = (g^b)^a = g^{ab} = (g^a)^b = s_{b}$ により Alice および Bob は共通の鍵を得られたことがわかります。

Computational Diffie-Hellman (CDH) 仮定

上記のプロトコルでは中間者は盗聴によって $A, B$ を得ることができますが、一般的には $A, B$ から $g^{ab}$ を計算するのは困難だと信じられているため、攻撃者は Alice と Bob が共有している秘密 $s_{a} = s_{b} = g^{ab}$ を知ることはできないと信じられています。
この「$A = g^a, B = g^b$ のみから $g^{ab}$ を計算するのは困難である」というのは未証明なのですが、これが正しいという仮定のことを一般的に「Diffie-Hellman (DH) 仮定」といいます。

この仮定は、秘密を計算できないという意味で Computational Diffie-Hellman (CDH) 仮定ということもあります。

CDH 仮定は DH 鍵共有方式の安全性の根拠となっているため、この仮定は DH 鍵共有方式にとって非常に重要になります。

おさらい：ElGamal 暗号

ElGamal 暗号は公開鍵暗号の黎明期に考案された公開鍵暗号方式です。公開鍵暗号としては RSA の方が圧倒的に有名ですが……。

ElGamal 暗号のプロトコルを以下に示します。

送信者の送信したいメッセージを $m (\in G)$ とします。
受信者は位数 $n$ 未満の乱数 $x$ を生成し、これを秘密鍵とします。また $X := g^x$ を公開鍵として公開します (または単に送信者へ送ります) 。
送信者は位数 $n$ 未満の乱数 $r$ を選択し、$c_1 := g^r$ および $c_2 := m \cdot X^r$ のふたつを受信者へ送ります。
受信者は $m' := c_1^{-x} \cdot c_2$ を計算し、メッセージを復号します。

Decisional Diffie-Hellman (DDH) 仮定

ElGamal 暗号では、盗聴者は $g^r$, $g^x$ の値を知りうることになりますから、CDH 仮定がもし破られてしまえばこのふたつの値から $g^{rx}$ を計算することで $c_2 \cdot (g^{rx})^{-1} = m$ を復元できてしまうことになります。
したがって、一見すると ElGamal 暗号は CDH 仮定に依存しているように思えます。
しかしある状況では ElGamal 暗号の安全性は CDH 仮定だけでは不十分です。

このことをみるために ElGamal 暗号でメッセージ $m$ が 1 ビットの場合、例えば $m = 1$ または $m = g$ の場合を考えてみましょう。
このとき、中間者が盗聴して得られるデータは $c_1 = g^r$ および $c_2 = g^{rx}$ $(m = 1 のとき)$ または $g^{rx+1}$ $(m = g のとき)$ です。
すると、もし中間者が「$g^r$ および $g^x$ が生成する Diffie-Hellman 秘密 $g^{rx}$ と $c_2$ が等しいかどうか？」を判定することができてしまうと、メッセージが復元できてしまうことになります！
ここで注意してほしいのは、この判定には DH 秘密 $g^{rx}$ が必ずしも計算できる必要がないことです。攻撃者が必要とするのは単に「与えられた $g^a, g^b, g^z \in G$ に対して $g^{ab} = g^z$ か？」というブール値のみです。

そこで CDH 仮定を少し緩めて「$A, B, X \in G$ が与えられたとき、$X$ はペア $A, B$ に対応する DH 鍵共有方式の秘密であるかどうかを判定するのは困難である」という仮定のことを Decisional Deffie-Hellman (DDH) 仮定といいます。判定するのが困難かどうかなので Decisional という単語をつけて CDH 仮定と区別します。

CDH 仮定と DDH 仮定の強弱関係

CDH 仮定と DDH 仮定は非常に似通ったものですが、これらの強弱関係をみてみましょう。
ここである仮定 A がある仮定 B より強いとは、仮定 A が成立するならば仮定 B も成立することをいいます。
強いて包含記号を用いると $A \subset B$ という感じでしょうか。A の方が B よりも狭いので、成り立つ確率が低いため、仮定としては強いという形になります。

さて、CDH 仮定と DDH 仮定の話に戻ると、結論から言えば「DDH 仮定の方が CDH 仮定より強い」といえます。
証明は非常に簡単なのでこれは読者の演習問題としておきます。

練習問題 1
DDH 仮定の方が CDH 仮定より強いことを証明せよ。

まとめ

(Computational) Diffie-Hellman 仮定

与えられた $g^a, g^b$ から $g^{ab}$ を計算するのが困難である、という仮定。

Diffie-Hellman 鍵共有方式の安全性の根拠。

Decisional Diffie-Hellman 仮定

与えられた $g^a, g^b, g^z$ に対し、$g^{ab} = g^z$ であるかどうかを判定するのが困難である、という仮定。

おまけ: Pairing

楕円曲線には Pairing (ペアリング) と呼ばれる関数が存在します。暗号の世界では BLS 署名などで使われますね。

ペアリングが効率的に計算できる楕円曲線については、実は DDH 問題は自明に解くことができます。
これはペアリングを $e(\cdot, \cdot): G \times G \rightarrow G_T$ (ここで $G_T$ はなんかの群) とかくと、$e(g^a, g^b) = e(g, g^z)$ をチェックすればいいだけです²。

この記事では群の二項演算を基本的に乗法的 (・) にあらわします。楕円曲線を利用する場合には加法的 (+) に書きますので、楕円曲線を利用する場合には適宜読み替えてください。 ↩
厳密に言うと $G$ と $G_T$ が単射 (?) じゃないと $e(g^a, g^b) = e(g^z)$ であっても $g^{ab} = g^z$ じゃない可能性もありますが、暗号学の文脈では $G$ と $G_T$ は同じ位数を持つ群と仮定することが多いです。 ↩