\( \def\vector#1{\boldsymbol{#1}} \)

ペアリング暗号

Takami Torao #Pairing #IBE #BLSSignature
  • このエントリーをはてなブックマークに追加

概要

ペアリング暗号 (pairing-based cryptography)双線形写像 (bilinear map) に基づく暗号アルゴリズム。2 つの暗号化群の元からある群への写像 \(e:G_1 \times G_2 \to G_3\) を使用する。

\(G_1\) と \(G_2\) を加法群、\(G_e\) を乗法群とし 3 群とも素数位数を \(p\) 持つとする。\(P \in G_1\) と \(Q \in G_2\) をそれぞれ \(G_1\) と \(G_2\) の生成元とする。このときペアリング演算は以下の特性を持つ写像 \(e:G_1 \times G_2 \to G_e\) である。

  • 双線形性: 全ての \(a, b \in \mathbb{Z}\) に対して \(e(aP, bQ) = e(P,Q)^{ab}\) が成り立つ。
  • 非退化: \(e(P,Q) \ne \vector{1}\) である。

実用目的では \(e\) は効率的に計算可能でなければならない。\(G_1=G_2=G_T\) の場合、ペアリングは対称である。\(G\) が環なら \(e\) は可換である。つまり任意の \(P,Q \in G\) に対して \(e(P,Q) = e(Q,P)\) である。良く知られているペアリングはヴェイユペアリング (Weil pairing) とテートペアリング (Tate pairing) である。

  1. 概要
    1. Weil ペアリングの性質
  2. ID ベース鍵共有
  3. ID ベース暗号
    1. 鍵生成局
  4. 三者間鍵共有
  5. BLS 署名
    1. ブラインド署名
    2. マルチ署名
    3. 署名集約
  6. 参考文献

Weil ペアリングの性質

ペアリングは楕円曲線や超楕円曲線上の 2 点をある有限体の元に変換する操作。2 つの係数 \(a, b\) を持つ 2 点 \(aP, bQ\) はペアリングによって \(g^{ab}\) に変換される。よく利用されてるのが楕円曲線を双線形写像とする Weil (ヴェイユ) ペアリング。

双線形 (bilinear)
\[ \begin{eqnarray*} e(P_1 + P_2, Q) & = & e(P_1, Q) e(P_2, Q) \\ e(P, Q_1 + Q_2) & = & e(P, Q_1) e(P, Q_2) \end{eqnarray*} \] つまり \(e(aP, Q) = e(P, aQ) = e(P, Q)^a\) であり、また \(e(P, Q) = e(P + O, Q) = e(P, Q) e(O, Q)\) より \(e(P, O) = e(O, Q) = 1\) となる。
同一性 (identify)
\[ e(P, P) = 1 \] 双線形性と合わせると \[ \begin{eqnarray*} e(P+Q, P+Q) & = & e(P,P) e(P,Q) e(Q,P) e(Q,Q) \\ & = & e(P,Q) e(Q,P) \\ & = & 1 \end{eqnarray*} \] より、\(e(P,Q) = e(Q,P)^{-1}\) の交代性 (alternating) を持つ。
非退化 (non-degenerate)
任意の \(Q\) に対して \(e(P, Q) = 1\) であれば \(P = O\) である。

ID ベース鍵共有

ペアリングを使ってそれぞれの主体に関連づけ公開されている ID 情報を公開鍵として鍵共有や公開鍵暗号を行うことができる。これは RSA や楕円曲線のような既存のスキームが鍵を生成した後に公開するのとは対照的に、公開情報から鍵を生成するという特徴を持っている。ID ベース鍵共有/公開鍵暗号には鍵生成局 (PKG; private key generator) と呼ばれる中央機構の存在を想定している。

ペアリング計算が可能な有限体上の楕円曲線 \(E/\mathbb{F}_q\) を定義する。鍵生成局はマスターキーに相当する秘密鍵 \(s \in \mathbb{Z}\) をランダムに選択する。

鍵生成
ハッシュ関数 \(H\) を用いて自分の ID を楕円曲線上にマッピングした値 \(P = H({\rm ID})\) を公開鍵とする。鍵生成局は公開鍵にマスター鍵 \(s\) を乗算した秘密鍵 \(S = s P\) を安全な方法でその ID 所有者に渡す。
鍵共有
鍵生成局より発行された秘密鍵を持つ A と B が共通の鍵を共有する方法について考える。A は B の ID から \(P_B = H({\rm B})\) を算出し自分の秘密鍵を使って \(K_{AB} = e(S_A, P_B)\) を計算する。同様に B は A の ID から \(P_A = H({\rm A})\) を計算して \(K_{BA} = e(P_A, S_B)\) を計算する。ここで \[ K_{AB} = e(S_A, P_B) = e(sP_A, P_B) = e(P_A, P_B)^s = e(P_A, sP_B) = e(P_A, S_B) = K_{BA} \] であることから両者は同一の値を共有している。

ハッシュ値が衝突したとき、つまり \(P_A = P_B\) のとき \(K_{AB} = K_{BA} = 1\) となり共有された値は公然となってしまうため \(H\) の結果は十分な大きさが必要である。また A と B が双線形写像 \(e\) 第一/第二パラメータのどちらに指定するかを双方での取り決めが必要がある。

ID ベース暗号

ID ベース鍵共有と同じ鍵生成スキームを使用して暗号化を行うことができる。鍵生成局は楕円曲線上のランダムな点 \(P\) を選び \((P, sP)\) を公開しているものとする。

暗号化
B から A に平文 \(m\) を暗号化して送信する。B はランダムに \(r\) を選択し以下を暗号文とする。\[ C = (C_1, C_2) = (rP, m \cdot e(rP_A, sP)) \]
復号化
\(C\) を受け取った A は秘密鍵 \(S_A = sP_A\) と \(C\) を使って以下の手順で平文 \(m\) を復元する。\[ \begin{eqnarray*} C_2 \cdot e(C_1, S_A) & = & m \cdot e(rP_A, sP) \cdot e(rP, sP_A) \\ & = & m \cdot e(P_A, P)^{sr} \cdot e(P_A, P)^{-sr} = m \end{eqnarray*} \]

他に Boneh and Franklin [1] による ID ベース暗号のスキームがある。

鍵生成局

上記の ID ベース鍵共有/暗号には中央的な鍵生成局が全ての主体の秘密鍵を知り得るという問題がある。これは鍵生成局をそれぞれが結託していない \(d\) 個に分散することで緩和することができる。具体的には、分散された鍵生成局のそれぞれから収集した \(\{s_1 P, \ldots, s_d P\}\) を合計した \(S = P \sum_{i=1}^d s_i = s P\) を秘密鍵として同様の操作を行うことができる。鍵生成局の全てが結託して \(s_i\) を持ち合わない限りマスター鍵となる \(s\) を復元することは困難である。またある鍵生成局から \(s_i\) が漏れたとしても残りの 2 つ以上の鍵生成局から鍵が漏れない限りマスター鍵を復元することは困難である。

もし ID に対応する主体が決まっているのであれば、全ての主体に秘密鍵を配布し終えた後にマスター鍵を廃棄するといった方法をとることができる。

三者間鍵共有

Diffie-Hellman 鍵共有をペアリングに応用したもので、1 ラウンドの通信で 3 者の間で共通の値を生成することができる。\(P\) と \(Q\) をそれぞれスキームパラメータとして公開する。

  1. A はランダムに \(a\) を選択し B と C に対して \((aP, aQ)\) を送信する。同様に B は \((bP, bQ)\) を、C は \((cP, cQ)\) を送信する。
  2. A, B, C は自分が持つ乱数と受信したデータを元にそれぞれ \(e(bP, cQ)^a\), \(e(cP, aQ)^b\), \(e(aP, bQ)^c\) を計算することで共通の値 \(e(P, Q)^{abc}\) を求めることができる。

超特異楕円曲線とディストーション写像 \(\hat{\phi}(\cdot)\) を用いることでパラメータの \(Q\) を削除して同様の操作が行えることがフェルフェールによって示されている。

BLS 署名

BLS 署名 [2] は Weil ペアリングを使用した電子署名スキームである。署名サイズの小ささを特徴に持ち、160 ビットで RSA 1024 ビット、DSA/ECDSA 320 ビット相当のセキュリティを提供する。また双線形写像の特徴を使って簡単なモデルでしきい値署名や署名集約へ応用することができる。

\(G\) と \(G_T\) を素数位数 \(q\) を持つ乗法群とし、\(g\) を群 \(G\) の生成元とした双線形写像 \(G \times G \to G_T\) を使用する。任意のバイナリを \(G\) にマップする \(H:\{0,1\}^* \to G\) を暗号論的ハッシュ関数とする。

鍵生成
まず秘密鍵 \(x = \mathbb{Z}_q\) をランダムに選択し、公開鍵を \(g^x\) とする。
署名
平文 \(m\) に対する署名 \(\sigma = H(m)^x\) を計算する。ここで、楕円曲線の素数位数を \(\log_2 q = 160\) となるように構成すれば署名 \(\sigma\) は 160 ビット程度の大きさとなる。
検証
平文 \(m\)、署名 \(\sigma\)、公開鍵 \(g^x\) を使用して以下が成り立てば署名は有効である。\[ e(\sigma, g) = e(H(m), g^x) \]

ブラインド署名

マルチ署名

署名集約

参考文献

  1. Dan Boneh, Matthew K. Franklin. Identity-Based Encryption from the Weil Pairing. Advances in Cryptology - Proceedings of CRYPTO 2001 (2001)
  2. Dan Boneh, Ben Lynn, Hovav Shacham. Short signatures from Weil pairing. Journal of Cryptology 17 (2004) (日本語訳)
  3. Lecture Notes on Control Systems
  4. John Bethencourt (2015) . ntro to Bilinear Maps