ペアリング
概要
楕円曲線上の離散対数問題を解くために用いられたことが発端
楕円曲線暗号の次の世代の暗号として研究が盛んに行われている公開鍵暗号の一種。
応用例として以下があげられる
2入力1出力関数で、双線形関数である
例：入力が楕円曲線上の2点、出力がある有限体の元
双線形であることが最もユニークな特徴
新たな暗号の誕生のきっかけになっている
代表的なペアリング
Tate Pairing
速い
Weil Pairing
古い
双線形DH問題を構成することができる
双線形群 $ (G_1, G_T, e)において $ P, P^a, P^b, P^cから$ e(P,P)^{abc}を求める問題
効率的に解く方法はまだ知られていない
暗号におけるペアリングの位置付け
https://gyazo.com/1d4aa1b41d5dda397856e4ae6206b46d
詳細
ペアリング関数 $ e : G_1 \times G_2 \rightarrow G_3
群 $ G_1, G_2, G_3
楕円曲線上の点 $ P = (x_1, y_2), Q = (x_2, y_2)
双線形性
$ e(P_1 + P_2, Q) = e(P_1, Q)\cdot e(P_2, Q)
$ e(P, Q_1 + Q_2) = e(P, Q_1)\cdot e(P, Q_2)
$ e(aP, bQ) = e(P, Q)^{ab} = e(bP, aQ)
非縮退性
$ \forall P, e(P, Q) = 1 \Rightarrow Q = O
$ \forall Q, e(P, Q) = 1 \Rightarrow P = O
https://gyazo.com/eae78d138632787138aa8a29e2bd7548
ペアリングの安全性
双線形計判定DH問題 → 双線形計算DH問題 → 離散対数問題
A → B：AはBに帰着する
結果的に離散対数問題を解くことに帰着する
ペアリングを用いた応用
任意の識別情報を用いて暗号化することができる公開鍵暗号
暗号化時に受信者が秘密鍵を持っている必要はない
後で秘密鍵生成局から受け取ることができる
MOV帰着
楕円曲線上の離散対数問題を解くために、有限体に射影することで計算時間を短くする方法
指数的計算量から準指数的計算量に変換
三者間公開鍵配送
三者間で共通鍵を配送する方法
自分以外の二者から公開鍵を得ることで、三者とも同じ共通鍵を計算することができる
$ (秘密鍵, 公開鍵) = (a, aP), (b, bP), (c, cP)
$ 共通鍵 = e(bP, cP)^a = e(aP, cP)^b = e(aP, bP)^c = e(P, P)^{abc}
ショート署名
署名長をより短くできる方法
署名は楕円曲線上の点であるので、法 q と同じ程度のビット長になる
署名者は V, P, Q を公開
$ V = sP
$ Q = sH(m)
検証者は以下が一致するか検証
$ e(V, H(m)) = e(P, Q)
署名が正しければ、双線形性により一致する
$ e(V, H(m)) = e(sP, H(m)) = e(P, sH(m)) = e(P, Q)
放送暗号
番組放送を特定のユーザにみに配信する場合に、一定の帯域を使用するだけで配信ができる方法
一般的に、限定配信対象のユーザーが増えれば、比例して使用する帯域が大きくなる
送信する暗号文を、特定ユーザ全員で復号して共通鍵を復元するイメージ
実装
TEPLA（University of Tsukuba Elliptic Curve and Library）
有限体上の元の計算
楕円曲線上の演算
ペアリング演算
筑波大学で配信されている
PBC Library
国際的には最も一般的
スタンフォード大学で配信されている
参考文献
報告書
ペアリングに関する最近の研究同行動向
岡本栄司 et al.
ペアリング暗号の実用化に向けて
岡本栄司
論文
ペアリングに基づく関数型暗号について
江藤恭平
スライド
Pairing の計算法とその実装
岡本栄司 筑波大学
新しい暗号技術
光成滋生
Web
双線形写像について