Jouxのヴェイユペアリングによる鍵交換アルゴリズムとは？双線形形式・歪み写像と決定的ディフィーヘルマン問題

なぜ3者間の鍵交換は難しいのか

標準的なディフィーヘルマン鍵交換は2者間のプロトコルです。楕円曲線上の生成点Pを公開し、 AliceはaPを、BobはbPを送り合い、それぞれがa(bP) = b(aP) = abPを計算することで、共有鍵abPに到達します。これを3者(Alice・Bob・Carol)に素朴に拡張しようとすると、通常は複数ラウンドの通信(例えば、まず2者間で鍵を作り、それを使ってさらに3人目と鍵交換する、といった手順)が必要になります。

2000年、Antoine Jouxは論文「A One Round Protocol for Tripartite Diffie–Hellman」で、 ヴェイユペアリング(Weil pairing)と呼ばれる、楕円曲線上の双線形写像を使うことで、 3者間の鍵交換をディフィーヘルマンと同じ「1ラウンド」(各自が1回ずつ公開値を送るだけ)で実現できることを示しました。楕円曲線暗号の数学的な基礎については別記事で扱っています。

ヴェイユペアリングという双線形形式

ヴェイユペアリングは、楕円曲線E上のn等分点群E[n]の2つの元を受け取り、 1のn乗根がなす群 μ_n の元を返す写像 e: E[n] × E[n] → μ_n です。重要な性質は次の3つです。

双線形性: e(aP, bQ) = e(P, Q)^(ab) が成り立つ。両方の変数について線形に振る舞う。
交代性: e(P, P) = 1。同じ点同士のペアリングは自明になる。
非退化性: Pが0でなければ、e(P, Q) ≠ 1 となるQが必ず存在する。

この「双線形性」こそが、Jouxのプロトコルの核心です。掛け算のような操作を、群の中の点(離散対数が困難な世界)に対して行いながら、指数部分だけを取り出して掛け合わせることができるからです。

歪み写像が必要な理由

ここで問題があります。交代性(e(P,P)=1)により、もし全員が同じ生成点Pの倍数 (aP, bP, cP)だけをやり取りする場合、これらは全てPが張る同一の巡回部分群に属するため、ペアリングの計算結果が自明になってしまう(非退化性が実質的に使えない)組み合わせが生じます。これを回避するために使われるのが歪み写像(distortion map)です。

歪み写像φは、E上の点Pを、Pとは線形独立な(Pの整数倍では表せない)別の点φ(P)へ、効率的に計算可能な形で送る写像です。Eric Verheulによって、超特異楕円曲線 (supersingular elliptic curve)上ではこのような歪み写像が具体的に構成できることが示されており、これによって「1つの生成点Pの倍数だけ」を公開値としてやり取りしても、 e(P, φ(P)) ≠ 1 となる非自明なペアリングを利用できるようになります。

鍵交換の計算方法

Jouxのプロトコルは、次のように進みます。楕円曲線E、生成点P、歪み写像φはあらかじめ公開されているとします。

Alice、Bob、Carolはそれぞれ秘密の整数 a、b、c を選ぶ。
それぞれ aP、bP、cP を計算し、これを(1ラウンドで)互いに公開する。
Aliceは e(bP, φ(cP))^a を計算する。
Bobは e(aP, φ(cP))^b を計算する。
Carolは e(aP, φ(bP))^c を計算する。

双線形性により、この3つの計算結果はすべて e(P, φ(P))^(abc) に一致します。こうして3者は、1ラウンドの通信だけで共有の秘密鍵 e(P, φ(P))^(abc) に到達します。従来のディフィーヘルマン型プロトコルでは複数ラウンドが必要だった3者間鍵交換を、 2者間の場合と変わらない通信量で実現している点が、この構成の独創性です。

補足：ペアリングは楕円曲線上のDDH問題を解いてしまう

ペアリングという道具には、鍵交換を可能にする一方で、重要な副作用があります。それが 決定的ディフィーヘルマン問題(Decisional Diffie-Hellman、DDH)との関係です。

通常のディフィーヘルマン鍵交換の安全性は、計算的ディフィーヘルマン問題(CDH) ―― P、aP、bPが与えられたとき、abPを計算するのは困難である ―― という仮定に基づいています。これに対しDDH問題は、P、aP、bP、cPが与えられたとき、「c ≡ ab (mod n) かどうかを判定する」という、より弱い(判定するだけでよい)問題です。

ペアリングが使える楕円曲線では、このDDH問題は効率的に解けてしまいます。 e(aP, bP) と e(cP, P) を計算して比較すればよいからです。双線形性により e(aP, bP) = e(P, P)^(ab)、e(cP, P) = e(P, P)^c であり、この2つが等しいことと ab ≡ c (mod n) が成り立つことは同値です。つまりペアリングを使えば、CDHは依然として困難なまま、DDHだけを多項式時間で解くことができてしまいます。

Gap Diffie-Hellman群: このように「DDHは易しいがCDHは困難」という性質を持つ群は、暗号理論においてGap-DHグループと呼ばれます。ペアリングが使える楕円曲線の多くはこの性質を持ちます。BLS署名などのペアリングベース暗号の多くは、この性質を逆手に取り、 DDHが解けることを積極的に利用しつつ、より強い仮定である 双線形ディフィーヘルマン問題(Bilinear Diffie-Hellman Problem、BDHP) ―― P、aP、bP、cPからe(P,P)^(abc)を計算するのは困難である ―― の困難性に安全性の根拠を置くように設計されています。Jouxの鍵交換プロトコルの安全性も、通常のCDHではなく、この双線形版の仮定に依拠しています。

まとめ

Jouxのプロトコル(2000年)は、ヴェイユペアリングの双線形性を利用し、3者間の鍵交換をディフィーヘルマンと同じ1ラウンドで実現する
ヴェイユペアリングは双線形性・交代性・非退化性を持つ写像 e: E[n]×E[n]→μ_n である
同一生成点の倍数だけでは非自明なペアリングが得られないため、超特異楕円曲線上で構成される歪み写像を使って線形独立な点を作る
各参加者は自分以外の2人の公開値と歪み写像を組み合わせてペアリングを計算し、双線形性により全員が同じ共有鍵e(P,φ(P))^(abc)に到達する
ペアリングは楕円曲線上のDDH問題を多項式時間で解いてしまうため、ペアリングベース暗号はCDHではなく、より強い双線形ディフィーヘルマン問題(BDHP)の困難性に安全性の根拠を置く