ペアリング写像
ペアリングとは
ペアリングとは，2入力1出力の関数であり，双線形性を持つ関数 (写像)である．
ペアリングは，最初楕円曲線暗号に対する攻撃手法として利用された．すなわち，楕円曲線上の離散対数問題の解法に用いられた．その後，ペアリングを用いた暗号方式が提案されるようになってきた．ペアリングの双線形性を利用すると，公開鍵として ID を利用する IDベース暗号や IDベース署名などが実現できる．
現在，暗号で利用されているペアリングは楕円曲線上で定義される関数であり，楕円曲線上の2点をを入力とし，ある有限体の元を出力とする関数である．楕円曲線上のペアリングには，Weil ペアリング， Tate ペアリング，およびそれらの変形ペアリングがある．
ペアリング演算は，既存の公開鍵暗号におけるべき乗剰余演算や楕円曲線暗号における楕円点のスカラー倍演算などと比較してより多くの計算コストを要するため，効率的なペアリング演算アルゴリズムが求められている．
双線形写像 (ペアリング)
演算 $\ast$ が定義された巡回群 $\mathbb{G}_1$ (単位元を $e_1$ とする)，演算 $\cdot$ が定義された巡回群 $\mathbb{G}_2$ (単位元を $e_2$ とする)，演算 $\sharp$ が定義された巡回群 $\mathbb{G}_T$ (単位元は $e_T$ とする) に対し
\[ e : \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T \]が双線型性，および非退化なる以下の2つの性質を満たす時，この写像 $e$ をペアリング写像と呼ぶ．
- 双線形性
任意の $u,\ u_1,\ u_2 \in \mathbb{G}_1,\ v,\ v_1,\ v_2 \in \mathbb{G}_2$ に対し以下の2つが成り立つ． \[ e (u_1 \ast u_2, v) = e (u_1, v)\ \sharp\ e (u_2, v) \] \[ e (u, v_1 \cdot v_2) = e (u, v_1)\ \sharp\ e (u, v_2) \] - 非退化
任意の $v \in \mathbb{G}_2$ に対し $e (u, v) = e_T (u \in \mathbb{G}_1)$ であるならば，$u = e_1$ である．
任意の $u \in \mathbb{G}_1$ に対し $e (u, v) = e_T (v \in \mathbb{G}_2)$ であるならば，$v = e_2$ である．
ペアリング写像の定義から次の関係が導かれる．
任意の整数 $a,\ b \in Z$ に対し
\[ e (u^a, v^b) = e (u^b, v^a) = e (u, v)^{ab} \]が成り立つ．
また，巡回群 $\mathbb{G}_2$ から $\mathbb{G}_1$ への写像 $ψ : \mathbb{G}_2 \rightarrow \mathbb{G}_1$ が同型写像であるとき，任意の $u,\ v \in \mathbb{G}_2$ に対し
\[ e (ψ(u), v) = e (ψ(v), u) \]が成り立つ．
ペアリングのタイプ
ペアリングは，効率的に計算できる同型写像
\[ ψ_1 : \mathbb{G}_1 \rightarrow \mathbb{G}_2 \] \[ ψ_2 : \mathbb{G}_2 \rightarrow \mathbb{G}_1 \]の存在の有無に応じて，次のの 3 タイプに分けられる．
- $\mathbb{G}_1 = \mathbb{G}_2$，すなわち $ψ_1$ 及び $ψ_2$ が共に存在する．
対称ペアリングと呼ばれる．対称ペアリングでは，標数3の有限体上の楕円曲線を用いること等により，高速なペアリング演算が実現できる利点ある．また，対称ペアリングでは，効率的な $ψ_1$ や $ψ_2$ を用いることで，暗号系構成や安全性証明が行われることがある．しかし，限定された楕円曲線しか使用できないことにより，柔軟なセキュリティレベルの設定ができないなどの不利な点も存在する． - $\mathbb{G}_1 \ne \mathbb{G}_2$ かつ $ψ_2$ が存在する（$ψ_1$ の存在は知られていない）．
非対称ペアリングと呼ばれる．非対称ペアリングでは，タイプ 1 と異なり，埋め込み次数や群位数に関して比較的制限がなくパラメータ生成ができるのが利点である．しかし，群 $\mathbb{G}_2$ へ直接写像するハッシュ関数が構成できない場合があり，そのようなハッシュ関数が必要な暗号系構成においては不利となる場合がある． - $\mathbb{G}_1 \ne \mathbb{G}_2$ かつ $ψ_1$ 及び $ψ_2$ の存在が知られていない．
非対称ペアリングと呼ばれる．パラメータ生成に関しタイプ 2 と同様の利点を有すると共に，群 $\mathbb{G}_2$ へのハッシュ関数が構成できる．しかし，$ψ_2$ が存在しないために，暗号プロトコルが構成できなかったり，安全性証明が成立しない場合があるなど不利な場合もある．
ペアリングを用いた暗号の安全性
楕円ペアリングを用いた暗号方式は，以下の問題の安全性に根拠を置いている．
- 双線形計算DH問題(BCDH)
楕円曲線上で与えられた入力の点の組 $(P, aP, bP, cP)$ に対して，$e (P, P)^{abc}$ を計算すること． - 双線形判定DH問題(BDDH)
楕円曲線上で与えられた入力の点の組 $(P, aP, bP, cP, T)$ に対して，$T = e (P, P)^{abc}$ か否かを判定すること．
これらは，次の有限体上で定義された問題の楕円ペアリング版である．
- 計算DH問題(CDH)
有限体上で与えられた入力の組 $(g, g^a, g^b)$ に対して，$g^{ab}$ を計算すること． - 判定DH問題(DDH)
有限体上で与えられた入力の組 $(g, g^a, g^b, T)$ に対して，$T = g^{ab}$ か否かを判定すること．
また，多くの暗号の安全性の基礎となるのは次の有限体上の離散対数問題である．
- 離散対数問題(DL)
有限体上で与えられた入力の組 $(g, g^a)$ に対して，$a$ を計算すること．
これらの問題の困難さには次の依存関係があり，帰着関係と呼ばれる．
- 離散対数問題が解ければ，計算DH問題が解ける．
- 計算DH問題が解ければ，判定DH問題が解ける．
- 判定DH問題が解ければ，双線形判定DH問題が解ける．
- 双線形計算DH問題が解ければ，双線形判定DH問題が解ける．
暗号プロトコルの設計に関しては，これらの問題がすべて困難であるとしている．
／