BLS signature や BN signature に必要な pairing 写像の実例である、optimal ate pairing について書く。[Ver2008] の流れに乗って説明する。
pairing 写像: 写像
- 双線型性:
$e(P_1 - P_2, Q) = e(P_1, Q)e(P_2, Q)^{-1}$ かつ$e(P, Q_1 - Q_2) = e(P, Q_1)e(P, Q_2)^{-1}$ - 非退化性:
$e(P, Q) \neq 1$ なる$P, Q$ が存在すること
(登場する群はすべてアーベル群であるが、典型的には
因子: 零点や極の情報を簡潔に表すためのもの。 形式的な定義は Wikipedia を見ること。以下は非形式的な記述のみを行う。
以下は楕円曲線の上のことだけを考える。
- 係数の和が 0: 例えば
$2[P] - [O]$ のような divisor は$\mathrm{div}(f)$ としては得られない。 - 係数の重みつき和が
$O$ :$[P] + [Q] - [P + Q]$ のような divisor は重みつき和が$P + Q - (P + Q) = O$ なので OK。$[P] - [O]$ は重みつき和が$P - O = P$ なので、$P \neq O$ のときは$\mathrm{div}(f)$ としては得られない。
無限遠点での ord をどう求めるべきか?
- 係数の和が 0 であることを利用する:
$P = (a, b)$ に対して$\mathrm{div}(x - a) = [P] + [-P] - 2[O]$ である。$[O]$ の係数 -2 は他の項の係数の和が 2 であることから導出できる。 - 正攻法。
$\mathrm{ord} _ {O}(x) = -2$ と$\mathrm{ord} _ {O}(y) = -3$ を利用する。これ自体は Riemann-Roch の定理によって構成できるようである。([ACDFLNV2006] の 4.4.2.a を参照)
フロベニウス写像
具体的な構成は https://hackmd.io/@jpw/bn254 や https://hackmd.io/@benjaminion/bls12-381 が参考になる。ここでは [Ver2008] の Section 2.1 に沿うことにする。
前提条件として以下がある。
$k \ge 2$ -
$q$ は素数ベキ -
$E$ は楕円曲線 -
$r$ は$r \mid #E(\mathbb{F} _ {q})$ なる素数 $r | q^k - 1, r^2 \not | q^k - 1$ -
$G _ 1 = E(\mathbb{F} _ {q^k})[r]$ ,$G _ 2 = E(\mathbb{F} _ {q^k})/rE(\mathbb{F} _ {q^k})$ ,$G _ T = \mathbb{F} _ {q^k}^{\ast}$
まずは基本的な関数から。
-
$l_{P, Q}$ :$P, Q$ を通る直線において 0 をとるような関数 -
$v_P$ :$P$ と$-P$ を通る直線において 0 をとるような関数 ($x - P_x$ )
これらの関数の因子は以下である:
$\mathrm{div}(l_{P, Q}) = [P] + [Q] + [-(P + Q)] - 3[O]$ $\mathrm{div}(v_P) = [P] + [-P] - 2[O]$
続いて Miller function
- 要件:
$\mathrm{div}(f_{s,P}) = s[P] - [sP] - (s-1)[O]$ - 定義:
$f_{1,P} := 1, f_{i+j,P} := f_{i,P}f_{j,P} l_{iP,jP}/v_{(i+j)P}$
こうすると
Barreto-Naehrig curve では以下のようにパラメータが決められている。
$x \in \mathbb{Z}$ $k = 12$ $q = p = 36x^4 + 36x^3 + 24x^2 + 6x + 1$ $r = p - 6x^2 = 36x^4 + 36x^3 + 18x^2 + 6x + 1$
その一種、BN254 では以下のようにパラメータが決められている。
-
$E$ は$y^2 = x^3 + 3$ x = 4965661367192848881 = 0x44e992b44a6909f1 ~= 2^{62.1}
BLS curve では以下である。(https://hackmd.io/@benjaminion/bls12-381)
$x \in 1 + 3\mathbb{Z}$ $k = 12$ $q = p = (x-1)^2(x^4 - x^2 + 1)/3 + x$ $r = x^4 - x^2 + 1$
その一種、BLS12-381 では以下である。
-
$E$ は$y^2 = x^3 + 4$ x = -0xd201000000010000
[Ver2008] の Sections 2.2, 4 に沿うことにする。
ここで唐突だが、Barreto-Naehrig curve では
以上をまとめると、
繰り返しになるがここで
BLS curve については、https://static1.squarespace.com/static/5fdbb09f31d71c1227082339/t/5ff394720493bd28278889c6/1609798774687/PairingsForBeginners.pdf を読む限り
[Ver2008] の 2.1:
ペアリングの型が
-
$P$ は$rP = O$ を満たす必要あり: こうすると$\mathrm{div}(f_{r, P}) = r[P] - r[O]$ が成立する -
$Q$ は$rE(\mathbb{F} _ {q^k})$ の差を無視できる:$f_{r, P}$ は群の準同型なので引数の$rE(\mathbb{F} _ {q^k})$ の差は結果の$(\mathbb{F} _ {q^k}^{\ast})^r$ の差として現れ、この差は$(q^k-1)/r$ 乗すると消える。
[Naeh2009] の Prop. 1.33 から、
[Ver2008] の 2.2:
[Ver2008] の 4:
Twisting とは何?
[Ver2008] の 2.2:
[Ver2008] の 2.3:
- 関数が normalized であるとは、
$u_O = -y/x$ として$u_O$ でローラン展開したときの首項の係数が 1 であることである。 -
$l_{P,Q}$ も$v_P$ も、しかるべき関数であって normalized であるものと定義する。($l_{P,Q}$ は$l_{P,Q} = 0$ が$P,Q$ を通る直線であるような多項式、$v_P$ は$v_P = 0$ が$P, -P$ を通る直線であるような多項式である。)-
$v_P$ =$x - x_P$ とすれば$(x-x_P)(-y/x)^{-2} \to 1$ であるため normalized である。 -
$P,Q$ を通る直線が$l_{P, Q} = ax + by + c = 0$ として、$l_{P, Q}$ が normalized であることは$b \neq 0$ のときは$b = -1$ 、$b = 0$ のときは$a = 1$ と同値のはず。
-
[Ver2008]: Frederik Vercauteren. Optimal pairings. Cryptology ePrint Archive, Report 2008/096, 2008.
[Naeh2009]: Michael Naehrig. Constructive and Computational Aspects of Cryptographic Pairings.
[ACDFLNV2006]: R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, and F. Vercauteren. Handbook of elliptic and hyperelliptic curve cryptography. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2006.
[FR1994]: G. Frey and H-G. Rück. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comp., 62(206):865–874, 1994.
[Mill2004]: V. S. Miller. The Weil pairing, and its efficient calculation. J. Cryptology, 17(4):235–261, 2004.