ペアリング写像

ペアリングとは

ペアリングとは,2入力1出力の関数であり,双線形性を持つ関数 (写像)である.

ペアリングは,最初楕円曲線暗号に対する攻撃手法として利用された.すなわち,楕円曲線上の離散対数問題の解法に用いられた.その後,ペアリングを用いた暗号方式が提案されるようになってきた.ペアリングの双線形性を利用すると,公開鍵として ID を利用する IDベース暗号や IDベース署名などが実現できる.

現在,暗号で利用されているペアリングは楕円曲線上で定義される関数であり,楕円曲線上の 2点をを入力とし,ある有限体の元を出力とする関数である.楕円曲線上のペアリングには,Weil ペアリング, Tate ペアリング,およびそれらの変形ペアリングがある.

ペアリング演算は,既存の公開鍵暗号におけるべき乗剰余演算や楕円曲線暗号における楕円点のスカラー倍演算などと比較してより多くの計算コストを要するため,効率的なペアリング演算アルゴリズムが求められている.

双線形写像 (ペアリング)

演算 * が定義された巡回群 G1 (単位元を e1 とする), 演算 ・ が定義された巡回群 G2 (単位元を e2 とする),演算 # が定義された巡回群 GT (単位元は eT とする) に対し

写像 e : G1 × G2GT

が双線型性, および非退化なる以下の 2つの性質を満たす時, この写像 e をペアリング写像と呼ぶ.

ペアリング写像の定義から次の関係が導かれる.

任意の整数 a, bZ に対し

 e (ua, vb) = e (ub, va) = e (u, v)ab

が成り立つ.

また, 巡回群 G2 から G1 への写像 ψ : G2G1 が同型写像であるとき,任意の u, vG2 に対し

 e (ψ(u), v) = e (ψ(v), u)

が成り立つ.

ペアリングのタイプ

ペアリングは,効率的に計算できる同型写像

 ψ1 : G1G2

 ψ2 : G2G1

の存在の有無に応じて,次のの 3 タイプに分けられる.

  1. G1 = G2,すなわち ψ1 及び ψ2が共に存在する.
    対称ペアリングと呼ばれる. 対称ペアリングでは,標数 3 の有限体上の楕円曲線を用いること等により,高速なペアリング演算が実現できる利点ある.また,対称ペアリングでは,効率的な ψ1ψ2 を用いることで,暗号系構成や安全性証明が行われることがある.しかし,限定された楕円曲線しか使用できないことにより,柔軟なセキュリティレベルの設定ができないなどの不利な点も存在する.
  2. G1G2 かつ ψ2 が存在する(ψ1 の存在は知られていない).
    非対称ペアリングと呼ばれる. 非対称ペアリングでは,タイプ 1 と異なり,埋め込み次数や群位数に関して比較的制限がなくパラメータ生成ができるのが利点である.しかし,群 G2 へ直接写像するハッシュ関数が構成できない場合があり,そのようなハッシュ関数が必要な暗号系構成においては不利となる場合がある.
  3. G1G2 かつ ψ1 及び ψ2 の存在が知られていない.
    非対称ペアリングと呼ばれる. パラメータ生成に関しタイプ 2 と同様の利点を有すると共に,群 G2 へのハッシュ関数が構成できる. しかし, ψ2 が存在しないために,暗号プロトコルが構成できなかったり,安全性証明が成立しない場合があるなど不利な場合もある.

ペアリングを用いた暗号の安全性

楕円ペアリングを用いた暗号方式は,以下の問題の安全性に根拠を置いている.

これらは,次の有限体上で定義された問題の楕円ペアリング版である.


また,多くの暗号の安全性の基礎となるのは次の有限体上の離散対数問題である.

これらの問題の困難さには次の依存関係があり,帰着関係と呼ばれる.

暗号プロトコルの設計に関しては,これらの問題がすべて困難であるとしている.

inserted by FC2 system