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

ペアリング暗号

2019年9月16日 #Pairing #IBE #BLS

概要

ペアリング暗号 (pairing-based cryptography) は双線形写像 (bilinear map) の構造を持った暗号アルゴリズム。楕円曲線暗号ではある同一の群 $G$ 上での写像 $e:G \times G \to G$ の写像だったが、ペアリングでは 2 つの暗号化群から別の群への写像 $e:G_1 \times G_2 \to G_T$ という構造を持つ。

$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 (ヴェイユ) ペアリングと Tate (テート) ペアリングであり、どちらも $G$ に楕円曲線やアーベル群多様体 (超楕円曲線) を使用する。

概要
1. Weil ペアリングの性質
BLS 署名
三者間鍵共有
ID ベース鍵共有
ID ベース暗号
1. 鍵生成局
参考文献

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$ である。

BLS 署名

BLS 署名 [2] は Weil ペアリングを使用した電子署名スキーム。元々の論文が「手書きで写せる大きさの電子署名」と述べているように署名サイズの小ささを特徴に持っており、セキュリティの強度は 160 ビットの署名サイズで RSA 1024 ビット、DSA/ECDSA 320 ビットに相当する。

$G_1$ , $G_2$ と $G_T$ を素数位数 $q$ を持つ乗法群とし、 $g$ を群 $G$ の生成元とした双線形写像 $G_1 \times G_2 \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)$

検証時の署名 $\sigma$ と公開鍵 $g^x$ がそれぞれ $G_1$ , $G_2$ 上に位置することに注意。通常の楕円曲線署名のスキームはある群 $G$ 上の (鍵や署名を表す) 元から同一の群 $G$ への変換 $e:G \times G \to G$ であるため、セキュリティを高めるために群 $G$ を大きくすると鍵や署名サイズも大きくなる。一方で BLS 署名がベースとしている双線形写像 $e:G_1 \times G_2 \to G_T$ は、直感的には、公開鍵の群 $G_2$ を大きくすればセキュリティに関連する群 $G_T$ の大きさを維持したまま署名の群 $G_1$ を小さくすることができる。また同じ考え方で $G_1$ と $G_2$ を逆にすれば公開鍵の方を小さくすることもできる。

マルチ署名

署名集約

三者間鍵共有

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

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

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

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 ベース鍵のスキームを導入する。ドローンにコントローラの ID を設定することで "自社製" かつ "意図した" コントローラー以外とは通信できないようにすることができる (ただし PKI を使っても同様なスキームは構築できるだろう)。

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

参考文献

Dan Boneh, Matthew K. Franklin. Identity-Based Encryption from the Weil Pairing. Advances in Cryptology - Proceedings of CRYPTO 2001 (2001)
Dan Boneh, Ben Lynn, Hovav Shacham. Short signatures from Weil pairing. Journal of Cryptology 17 (2004) (日本語訳)
Lecture Notes on Control Systems
John Bethencourt (2015) . ntro to Bilinear Maps
Guide to Pairing-Based Cryptography (Chapman & Hall/CRC Cryptography and Network Security Series)