双線形（ペアリング）について
※ 全体的に自分が理解しやすいように変数名を変えているので出典元と異なる場合があるので注意。
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
また、上記2楕円曲線のに対して、有限体$ \bold{F}_pを定める。
さらに、位数$ pの乗法巡回群（$ 1の$ p乗根の集合）として、$ G_Tを定める。
このとき、$ a, b \in \bold{F}_pなる$ a ,bに対して、写像$ e: G_1 \times G_2 \to G_Tが以下を満たすことを 双線形という？（結論から言うとこれが定義。でも知らないフリをして先に進む）
$ e(aP, bQ) = e(P, Q)^{ab}
でも、P.22のBLS署名の最後「正当性」では、以下が登場している。（こっちが正しいと思う。同じことを言っている？）
$ e(sH(m), Q) = e(H(m), sQ)
物理のかぎしっぽ
（復習）
一変数関数に対して、 線形性とは、ベクトル空間$ 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}
では、二変数ではどうなるか。
タプル$ (x, y)をベクトル空間$ Vの直積集合$ V \times Vの元と考えて、写像$ \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)
双線形関数は 個々の変数に対して別々に線形性を持っている と言えそうです．これが双線形という名前の由来でもあります
なるほど。確かにそう見える。
岸本研究室 - 双線形写像について
上記の双線形について、こちらにあった満たすべき性質のほうがわかりやすいかも。上記、物理のかぎしっぽは以下が複合して表現しただけなので、式の数は多いが、こちらのほうがシンプルで学習するときは良かった。
ベクトル空間$ 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)
こちらのほうが「個々の変数に対して別々に線形性を持っている」というのがわかりやすいと思う。
双線形の例を考える
「例示は理解の試金石」ということで双線形を満たす写像$ fを考えてみる。
（双線形な例）
$ f(x, y) = xy
上記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式中の一番上の式で確認して、だめだねってなろう。
$ (l.h.s) = f(x_1 + x_2, y) = (x_1 + x_2) + y
$ \begin{array}{l} (r.h.s) &=& f(x_1, y) + f(x_2, y) \\ &=& (x_1 + y) + (x_2 + y) \\ &=& (x_1 + x_2) + y + y \\ &=& f(x_1 + x_2, y) + y \end{array}
となり、左辺と右辺が一致しない。
ブロックチェーン系プロジェクトで着目される暗号技術（再訪）
再び戻ってきた。ところで、先程の4式について。
$ 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と有限体$ \bold{F}_pで考え直す必要がある。
写像$ e: G_1 \times G_2 \to G_Tと$ a \in \bold{F}_pについて考える。
$ e: G_1 \times G_2 \to G_Tなる写像について、
$ u \in G_1, v \in G_2, a, b \in \mathbb{Z}に対して、
$ e(u^a, v^b) = e(u, v)^{ab}
が成り立つことである。ただし、このとき$ eは非退化である。 $ \forall P \in G_1, \forall Q \in G_2, \forall a, b \in \mathbb{Z} に対して、
$ e(aP, bQ) = e(P, Q)^{ab}
と表現されることもある。
これが欲しかった表記。
ベクトル空間から乗法巡回群への議論で少し飛んでしまっているように感じられるので補足。
4式のうち、上2式について対応を示す。($ yについては同様なので省略）
$ f(x_1 + x_2, y) = f(x_1, y) + f(x_2, y) (1)
$ f(cx, y) = c f(x, y) (2)
式(2)から示す。$ e(aP, bQ) = e(P, Q)^{ab}において、$ a = c, b = 1とすると
$ e(cP, Q) = e(P, Q)^{c}
と表現できる。ここで$ e(P, Q) \in G_Tで$ G_Tが乗法巡回群であることを考えると自然な表記であろう。
次に式(1)について。$ P \in G_1で$ G_1が加法巡回群であることを考えると
$ e(P_1 + P_2, Q) = e(P_1, Q)e(P_2, Q)
となることを示せればよい。ここで$ P_1, P_2は$ G_1の元であることから生成元$ Pを用いて、
$ P_1 = a_1 P
$ P_2 = a_2 P
と表現できる。ここで$ a_1, a_2 \in \mathbb{Z}である。よって、
$ \begin{array}{l} e(P_1 + P_2, Q) &=& e(a_1P+a_2P, Q) \\ &=& e((a_1+a_2)P, Q) \\ &=& e(P, Q)^{(a_1+a_2)} \\ &=& e(P,Q)^{a_1} e(P,Q)^{a_2} \\ &=& e(a_1 P,Q) e(a_2 P, Q) \\ &=& e(P_1, Q) e(P_2, Q) \end{array}
が得られる。
ここまでの議論が、整数$ \mathbb{Z}から有限体$ \mathbb{F}_b上でも成り立つとして
$ \forall P \in G_1, \forall Q \in G_2, \forall a, b \in \mathbb{F}_p に対して、
$ e(aP, bQ) = e(P, Q)^{ab}
である。ここから$ a, bが可換であることがわかるが、もう少し詳細に書いておく。
$ c \in \mathbb{F}_pに対して、$ a = c, b = 1とすると
$ e(cP, Q) = e(P, Q)^c
である。同様に$ a = 1, b = cとすると
$ e(P, cQ) = e(P, Q)^c
である。これらを合わせると
$ e(cP, Q) = e(P, cQ)
$ e(sH(m), Q) = e(H(m), sQ)
References