Computational Diffie-Hellman (CDH) 仮定と Decisional Diffie-Hellman (DDH) 仮定

Diffie-Hellman (DH) 鍵共有方式は最新の SSL (TLS) である TLS v1.3 では[唯一の鍵共有方式となっている](https://ja.wikipedia.org/wiki/Transport_Layer_Security#%E9%8D%B5%E5%85%B1%E6%9C%89)くらい浸透してきた暗号技術かと思います。
皆さん名前ぐらいは聞いたことあるのではないでしょうか？

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

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

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

[^1]: この記事では群の二項演算を基本的に乗法的 (・) にあらわします。楕円曲線を利用する場合には加法的 (+) に書きますので、楕円曲線を利用する場合には適宜読み替えてください。

1. Alice は $n$ 未満の任意の乱数 $a$ を生成し、$g^a =: A$ を Bob へ送ります。
1. Bob も同様に $n$ 未満の任意の乱数 $b$ を生成し、$g^b =: B$ を Alice へ送ります。また、$s_{b} := A^b$ を共通の鍵として保管します。
1. Alice は $s_{a} := B^a$ を共通の鍵として保管します。
1. $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 暗号のプロトコルを以下に示します。

1. 送信者の送信したいメッセージを $m (\in G)$ とします。
1. 受信者は位数 $n$ 未満の乱数 $x$ を生成し、これを秘密鍵とします。また $X := g^x$ を公開鍵として公開します (または単に送信者へ送ります) 。
1. 送信者は位数 $n$ 未満の乱数 $r$ を選択し、$c_1 := g^r$ および $c_2 := m \cdot X^r$ のふたつを受信者へ送ります。
1. 受信者は $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 署名](https://ja.wikipedia.org/wiki/%E3%83%9C%E3%83%8D%E3%83%BB%E3%83%AA%E3%83%B3%E3%83%BB%E3%82%B7%E3%83%A3%E3%83%81%E3%83%A3%E3%83%A0%E7%BD%B2%E5%90%8D)などで使われますね。

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

[^2]: 厳密に言うと $G$ と $G_T$ が単射 (?) じゃないと $e(g^a, g^b) = e(g^z)$ であっても $g^{ab} = g^z$ じゃない可能性もありますが、暗号学の文脈では $G$ と $G_T$ は同じ位数を持つ群と仮定することが多いです。