BLS署名における双線形性（ペアリング）について

ブロックチェーン系プロジェクトで着目される暗号技術のP.21-22を理解するために双線形性（ペアリング）について調べた。自分が理解するに至った軌跡をメモベースで残す。

余談だが、調べる過程で双線形写像（Bilinear maps）とペアリングの違いが気になった。個人的な印象としては、ペアリングは暗号分野寄りに使われる用語だと思ったが、Intro to Bilinear Mapsにも以下のように書いてあるので、本記事では大体同じものとして扱う。

Bilinear maps are called pairings because they associate pairs of elements from G1 and G2 with elements in Gt.

(拙訳) 双線形写像はペアリングとも呼ばれる。 G1とG2からの要素をGtでペアとして関連付けるからだ。

以下、調べた内容。¹

双線形とは何なのか

本節は、ブロックチェーン系プロジェクトで着目される暗号技術がベースとなっている。

双線形を定義するにあたり、まず2種類の楕円曲線の生成元を $P, Q$ とする。このとき、素数位数 $p$ の加法巡回群 $G_1, G_2$ は、以下のように表現できる。

$G_1 = \lbrace 0, P, 2P, ..., (p-1) P \rbrace$
$G_2 = \lbrace 0, Q, 2Q, ..., (p-1) Q \rbrace$

また、有限体 $\mathbb{F}_p$ と、位数 $p$ の乗法巡回群（ $1$ の $p$ 乗根の集合）として $G_T$ を定める。

このとき、 $a, b \in \mathbb{F}_p$ なる $a ,b$ に対して、写像 $e: G_1 \times G_2 \to G_T$ が以下を満たすことを双線形という。

$e(aP, bQ) = e(P, Q)^{ab}$

個人的に本記事を書く要因となったのが、ブロックチェーン系プロジェクトで着目される暗号技術P.22「正当性」における以下の数式。上記定義と表記が違ったので疑問に思って調べ始めた。なので本記事では下記数式が成立するところまでを追う。

$e(sH(m), Q) = e(H(m), sQ)$

ベクトル空間における線形性（その1）

本節は、双線形関数物理のかぎしっぽがベースになっている。

まず、復習として一変数関数に対する線形性を考える。これはベクトル空間 $V$ の $x, y \in V$ なる元に対して、写像 $\phi: V \to \mathbb{R}$ が以下を満たすことだった。

$\phi(x + y) = \phi(x) + \phi(y)$
$\phi(\alpha x) = \alpha \phi(x) , \alpha \in \mathbb{R}$

では、二変数ではどうなるか。ベクトル空間 $V$ の直積集合 $V \times V$ の元 $(x, y)$ に対して、写像 $\psi(x,y): V \times V \to \mathbb{R}$ が以下を満たすことを双線形という。

$\psi(\alpha x + \beta x, y) = \alpha \psi(x, y) + \beta \psi(x,y)$
$\psi(x, \alpha y + \beta y) = \alpha \psi(x, y) + \beta \psi(x,y)$

双線形関数物理のかぎしっぽ本文には、以下のように記載されているが、理解が及ばず腹落ちしなかった。

双線形関数は個々の変数に対して別々に線形性を持っていると言えそうです．これが双線形という名前の由来でもありますなるほど。確かにそう見える。

ベクトル空間における線形性（その2）

本節は、岸本研究室 - 双線形写像についてがベースとなっている。

上記議論では、理解が及ばなかったので、もう少しシンプルに考える。「ベクトル空間における線形性（その1）」の定義に比べて、式の数は多いが、以下で双線形を定義したほうがシンプルで、学習にあたっては、理解しやすかった。

双線形を定義する。ベクトル空間 $V$ を考え、 $x, x_1, x_2, y, y_1, y_2 \in V$ なる元を考える。このベクトル空間 $V$ に対して、 $f: V \times V \to \mathbb{R}$ なる写像 $f$ を定義する。また、 $c \in \mathbb{R}$ とする。このとき双線形は以下の性質を満たすことをいう。

$f(x_1 + x_2, y) = f(x_1, y) + f(x_2, y)$
$f(cx, y) = c f(x, y)$
$f(x, y_1 + y_2) = f(x, y_1) + f(x, y_2)$
$f(x, cy) = c f(x, y)$

こちらのほうが「ベクトル空間における線形性（その1）」で引用した個々の変数に対して別々に線形性を持っているというのが理解しやすいと思う。

双線形の例

「例示は理解の試金石」ということで双線形を満たす写像 $f$ の具体例を考えてみる。

双線形な例

$f(x, y) = xy$

「ベクトル空間における線形性（その2）」で定義した4式を一つずつ確かめていく。

$f(x_1 + x_2, y) = (x_1 + x_2) y = x_1 y + x_2 y = f(x_1, y) + f(x_2, y)$
$f(cx, y) = (cx)y = c xy = c f(x, y)$
$f(x, y_1 + y_2) = x(y_1 + y_2) = x y_1 + x y_2 = f(x, y_1) + f(x, y_2)$
$f(x, cy) = x(cy) = c xy = c f(x, y)$

となり、すべて満たすので双線形。

双線形じゃない例²

$f(x, y) = x + y$

実は最初にこれを念頭に考えていた。パッと見、線形性持ってそうだし。でも双線形じゃない。 4式中の一番上の式で双線形を満たさないことを確認する。

となり、左辺と右辺が一致しない。

BLS署名における双線形

話をベクトル空間から乗法巡回群で考えているBLS署名の話に戻す。それにあたり「ベクトル空間における線形性（その2）」で登場した双線形性の定義を再掲する。

$f(x_1 + x_2, y) = f(x_1, y) + f(x_2, y)$
$f(cx, y) = c f(x, y)$
$f(x, y_1 + y_2) = f(x, y_1) + f(x, y_2)$
$f(x, cy) = c f(x, y)$

これらはベクトル空間 $V$ と実数 $\mathbb{R}$ で考えていたので、乗法巡回群 $G_T$ と有限体 $\mathbb{F}_p$ で考え直す。Intro to Bilinear Mapsより双線形性の定義を引用すると、双線形性とは $e: G_1 \times G_2 \to G_T$ なる写像について、 $u \in G_1, v \in G_2, a, b \in \mathbb{Z}$ に対して、