Paring - BLS signature -

この先にはペアリングが待っており、ペアリングの先にはzkSNARKsやKate commitmentといったVerifiable Databaseの世界、Ethereum2.0やEthereum Layer2 zkRollupなどの次世代型ブロックチェーンの世界が広がっています
(中略)
多分このままこう進んでいけば行けば社会は暗号や数学で作られていくことになるんだと思います。

楕円曲線の夢の国に住もう！！

Pairing

r捻れ群

r捩れ点集合の定義

$$
E[r] \stackrel{\mathrm{def}}{=} \{P \in E(\bar K)\space| \space rP = O \space \}
$$

Kではなく代数的閉包$${\bar K}$$。全ての点が確実に位数rとなる。

$$
\bar F_{q} = \bigcup_{k > 1}{F_{q^{k}}}
$$

Tortion points

E[r]はr-tortion subgroup。

$$
E[r] := \{P \in E(F_q)\space| \space rP = O \space \}
$$

$$
\mu_r = \{\alpha \in \mathbb F_{q^k}  \space | \space \alpha^r = 1\}
$$

Weil paring

$$
e_r :=
  \begin{cases}
     {E[r] \times E[r] \to \mu_r }\ \\
     {(P, Q) \mapsto {f_p(Q + S)\cdot f_q(T)} {f_p(S) \cdot f_q(P + T) } }
  \end{cases}
$$

Optimal Ate Pairing

$${\pi_p}$$はFrobenius endomorphismである。

$$
\pi_p :=
  \begin{cases}
    {E \to E}\ \\
    {(x, y) \mapsto (x^p, y^p) }
  \end{cases} \\
$$

$$
\mathbb G_1 := E[r] \bigcap Ker(\pi_p - [1]) = E(\mathbb F_p)[r] \\
\mathbb G_2 :=E[r] \bigcap Ker(\pi_p - [p]) \subseteq E(\mathbb F_{p^{12}})[r] \\
e_r :=
  \begin{cases}
    {\mathbb G_1 \times \mathbb G_2 \to \mu_r}\ \\
    {(P, Q) \mapsto (f_{6t + 2, Q}(P)\cdot l_{[6t + 2]Q + \pi_{p}(Q),\pi_{P}Q}(P)\cdot l_{[6t + 2]Q + \pi_{p}(Q) + \pi_{P}Q, -\pi^{2}_{P}Q} (P))^{\frac{p^{12}-1}{r}} }
  \end{cases}
$$

High-Speed Software Implementation of the
Optimal Ate Pairing over Barreto–Naehrig
Curves

1.双線型性 (bilinearity)

$$
e_r(P_1 + P_2, Q) = e_r(P_1, Q)\cdot e_r(P_2, Q)
$$

$$
e_r(P , Q_1 + Q_2) = e_r(P, Q_1)\cdot e_r(P, Q_2)
$$

2.非退化性 (non-degeneracy)

$$
\forall Q \in E[r], s.t, e_r(P, Q) = 1 \Rightarrow P = O
$$

$$
\forall P \in E[r], s.t, e_r(P, Q) = 1 \Rightarrow Q = O
$$

3.交代性 (alternating)

$$
\forall P \in E[r], s.t, e_r(P, P) = 1
$$

4.歪対称性 (skew symmetry)

$$
\forall P, Q \in E[r], s.t, e_r(P, Q) = e_r(Q, P)^{-1}
$$

5.ガロア作用 (Galois action)

$$
\forall \tau \in Gal(K/\bar{K}), s.t, e_r(\tau P, \tau Q) = \tau e_r(P, Q)
$$

P, Qが線型従属の時、$${Q = kP}$$と表せる。

tiribial pair

$$
\forall P, Q \in E[r], kP = Q, s.t, e_r(P, Q) = e_r(P, kP) = e_r(P, P)^{k} = e_r(P, P) \cdots e_r(P, P) = 1
$$

example: 双線形性

$$
e(x, y) := 2^{xy}
$$

$$
e(3, 5 + 7) = e(3, 5)\times e(3, 7)
$$

$$
(\because left\space side = e(3, 5 + 7) = 2^{3 \times (5 + 7)} = 2^{3 \times 5 + 3 \times 7} = 2^{3 \times 5} \cdot 2^{3 \times 7} = e(3, 5)\times e(3, 7) = right\space side)
$$

Application: BLS signature

NISTの引用によれば、ペアリングの性質を踏まえないと、必ずしも実用的ではない、作成者が想定しているほど効率的ではない実装になっちゃうよと。

However, if this approach is taken, then it is easy to make assumptions concerning the properties of pairings which are not necessarily correct, and hence develop cryptographic schemes which cannot be realized in practice, or which cannot be implemented as efficiently as the authors assume

Report on Pairing-based Cryptography

• s: secret ($${\in \mathbb Z/q \mathbb Z}$$)

• m: message

• H: hash func

• $${G_1}$$, $${G_2}$$: generator

$$
pubkey = sG_2
$$

$$
\sigma = sH(m)
$$

$$
e(\sigma,G_2) = e(H(m), sG_2)
$$

※ここで、$${ H(m) \in G_1 }$$としている。実際の実装では`hashToCurve()`と名付けられた関数を呼び出し、楕円曲線上に点を取るための処理を行う。曲線によってもアルゴリズムが異なっていたりと、研究開発が盛んな領域である。以下はbitcoin-coreの説明。cosmos-sdkも参考にしている実装。
https://github.com/bitcoin-core/secp256k1/blob/master/doc/ellswift.md
https://eprint.iacr.org/2022/759

two messages case:

Gen key

choose a random number 

$$
secretKey = s \\
s.t \space s \in \mathbb Z/q \mathbb Z
$$

$$
pubKey1 = s_1G_2
$$

$$
pubkey2 = s_2G_2
$$

Sign each msg

$$
\sigma_1 = s_1H(msg_1) \in G_1
$$

$$
\sigma_2 = s_2H(msg_2) \in G_1
$$

aggregate signature

$$
\sigma = \sigma_1 + \sigma_2
$$

Verify: each message is different

$$
e(\sigma ,G_2) == e(H(m_1) , pubKey_1)\cdot e(H(m_2) , pubKey_2)
$$

$$
\because left \space side = e(\sigma ,G_2) =  e(s_1 \cdot H(m_1) + s_2 \cdot H(m_2) ,G_2) =e(s_1 \cdot H(m_1), G_2)\cdot e(s_2 \cdot H(m_2), G_2) \\
right \space side = e(H(m_1) , pubKey_1)\cdot e(H(m_2) , pubKey_2)
= e(H(m_1) , s_1 G_2)\cdot e(H(m_2) , s_2 G_2)
$$

when each message is the same

$$
\sigma_1 = s_1\cdot H(m)
$$

$$
\sigma_2 = s_2\cdot H(m)
$$

Verify: each message is identical

$$
e(\sigma ,G_2) == e(H(m_1) , pubKey_1)\cdot e(H(m_2) , pubKey_2)
$$

各メッセージが同じ時、第一引数が同じなので双線形性の性質から、ペアリングの乗法の成分となる第二引数を$${G_2}$$上の加法演算として、次のように右辺を式変形できる。
こうすることで、$${G_1}$$上で集約した署名を$${G_2}$$上で集約した公開鍵を使用して、あたかも単一署名の検証と同じように検証できる。

$$
e(\sigma ,G_2) == e(H(m) , s_1G_2)\cdot e(H(m) , s_2G_2) \\
right \space side = e(H(m) , s_1G_2 + s_2G_2)) 
$$

$${ \because left \space side = e(s_1\cdot H(m) + s_2\cdot H(m), Q) = e((s_1 + s_2)H(m), Q) = e(H(m), Q)^{(s_1 + s_2)}= e(H(m), (s_1 + s_2)Q) = e(H(m), s_1Q + s_2Q)}$$

結果として、次のように一般化できる。

$$
e(\sum_{i=1}^n \sigma_i, G_2) == e(H(m), \sum_{i=1}^n pk_i) \\
(\because e(H(m), pk_1)\cdot e(H(m), pk_2) \cdots e(H(m), pk_n) = e(H(m), \sum_{i=1}^n pk_i))
$$

Implementation: bls library with mcl

Verify: each message is different

https://github.com/herumi/bls-eth-go-binary/blob/f61456b875d2649d0a9c58ed5f269c82d549672a/bls/eth.go#L172
https://github.com/herumi/bls/blob/3714b6072b44c4346ee96a3c1869fa86b964b101/src/bls_c_impl.hpp#L437

// AggregateVerify --
// len(msgVec) == 32 * len(pubVec)
// check all msgs are different each other
func (sig *Sign) AggregateVerify(pubVec []PublicKey, msgVec []byte) bool {
	return sig.innerAggregateVerify(pubVec, msgVec, true)
}

公開鍵の集約も署名の集約も配列に入れるけれど、順序を気にしなくても良い。
これは$${e(P_1 + P_2, Q) = e(P_2 + P_1, Q) = e(P_1, Q)\cdot e(P_2, Q)}$$の性質を使っているためである。

この処理のためにライブラリのこの関数を呼び出す。

https://github.com/herumi/bls-eth-go-binary/blob/master/bls/bls.go#L755-L764
go:

// Aggregate --
func (sig *Sign) Aggregate(sigVec []Sign) {
	var p *C.blsSignature
	if len(sigVec) == 0 {
		p = nil
	} else {
		p = &sigVec[0].v
	}
	C.blsAggregateSignature(&sig.v, p, C.mclSize(len(sigVec)))
}

hpp:

void blsAggregateSignature(blsSignature *aggSig, const blsSignature *sigVec, mclSize n)
{
	if (n == 0) {
		memset(aggSig, 0, sizeof(*aggSig));
		return;
	}
	*aggSig = sigVec[0];
	for (mclSize i = 1; i < n; i++) {
		blsSignatureAdd(aggSig, &sigVec[i]);
	}
}

Verify: each message is identical

go:

// FastAggregateVerify --
func (sig *Sign) FastAggregateVerify(pubVec []PublicKey, msg []byte) bool {
	if pubVec == nil || len(pubVec) == 0 {
		return false
	}
	n := len(pubVec)
	return C.blsFastAggregateVerify(&sig.v, &pubVec[0].v, C.mclSize(n), getPointer(msg), C.mclSize(len(msg))) == 1
}

呼び出し先のcppを見ると鍵は毎回集約される

公開鍵の集約:

https://github.com/herumi/bls-eth-go-binary/blob/master/bls/bls.go#L766-L773

https://github.com/herumi/bls/blob/3714b6072b44c4346ee96a3c1869fa86b964b101/src/bls_c_impl.hpp#L412
hpp:

// return -1 if some pubVec[i] is zero else 0
int blsAggregatePublicKey(blsPublicKey *aggPub, const blsPublicKey *pubVec, mclSize n)
{
	if (n == 0) {
		memset(aggPub, 0, sizeof(*aggPub));
		return 0;
	}
	int ret = 0;
	*aggPub = pubVec[0];
	if (cast(&pubVec[0].v)->isZero()) ret = -1;
	for (mclSize i = 1; i < n; i++) {
		if (cast(&pubVec[i].v)->isZero()) ret = -1;
		blsPublicKeyAdd(aggPub, &pubVec[i]);
	}
	return ret;
}

https://github.com/herumi/bls/blob/3714b6072b44c4346ee96a3c1869fa86b964b101/src/bls_c_impl.hpp#L428
hpp:

int blsFastAggregateVerify(const blsSignature *sig, const blsPublicKey *pubVec, mclSize n, const void *msg, mclSize msgSize)
{
	if (n == 0) return 0;
	blsPublicKey aggPub;
	int ret = blsAggregatePublicKey(&aggPub, pubVec, n);
	if (ret < 0) return 0;
	return blsVerify(sig, &aggPub, msg, msgSize);
}

BLS署名と検証のまとめ

ペアリングの性質

計算量:
複数メッセージに対して署名する場合、検証時にペアリングを呼び出す回数は
n個の複数メッセージが全て同じ時→1回
n個の複数メッセージがそれぞれ異なるとき→n回

ペアリングは内部で、millor loopを走らせたりfrobeniusしたり、とにかく重い処理を行なっている。呼び出し回数が多いと莫大な計算量を必要とする。

$${G_2}$$ について

メモリー:
$${G_2}$$の演算は、元の楕円曲線から複素数パラメータを使用した座標変換を行う。このため、通常の楕円曲線と比べてこの分のメモリを余分に消費する。割と膨大。

安全性の仮定

「多くの楕円曲線の暗号系はDLP, CDHPの仮定によっていて、ペアリングはbilinear Diffie-Hellman problem (BDHP)によっている。これはDLPやCDHPが解かれれば解かれるものなので、DLP, CDHPに比べて強くはない。」とNISTはレポートしている。

We end this section with some remarks on the security of pairing-based cryptography. Much of elliptic curve cryptography relies on the difficulty of two problems known as the discrete log problem (DLP) and the computational Diffie-Hellman problem (CDHP). These problems have been well studied, and if parameters are correctly chosen then they are believed to provide adequate security. The security assumption behind pairing-based cryptography is known as the bilinear Diffie-Hellman problem (BDHP). This is a much newer problem, which has not been as well-studied. It is known that if one can solve the DLP or CDHP then one can also solve the BDHP. So the security of pairing-based cryptography is not stronger than that of elliptic curve cryptography. There are no currently known attacks to break the BDHP, and it is the focus of much research.

TODO

Ethereumにはprecompileが入ってるっぽい。そのうち真面目にメモリとか計算スピードとか測定したい。

※ r捻れ点の集合の直積から1のm乗根の群$\mu_m$をペアリングの定義として自然に導かれるということをherumi-sanが多様体とかを使用して、示されてます。「ホモロジー代数入門とWeilペアリングの定義」。けどこれは知らなくてもコード読める。

Links

https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html

BLS Multi-Signatures With Public-Key Aggregation

High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves
Pairing-Friendly Elliptic Curves of Prime Order
A note on twists for pairing friendly curves

中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita

NIST report
https://leonahioki.medium.com/楕円曲線の夢の国に住もう-12dcc675995a

BLS12-381 For The Rest Of Us 日本語版
BLS12-381 For The Rest Of Us 原文

https://static1.squarespace.com/static/5fdbb09f31d71c1227082339/t/5ff394720493bd28278889c6/1609798774687/PairingsForBeginners.pdf

ガロア作用:

ガロア理論の基本定理 - Wikipedia

ガロア理論/Galois拡大 - Wikibooks

ガロア群 - Wikipedia

keywords

Z / m Z の標数は m である。
有限体(ガロア体)は必ず正標数を持つ
代数的閉包は代数的に閉じているKの代数拡大であって、実数体の代数的閉包は複素数体
Gal()はガロア拡大の意味。例は$${Gal(\mathbb Q(√2)/\mathbb Q)}$$