鍵生成 : $s \in 𝔽_r$ をランダムにとり署名鍵とし、検証鍵を $pk:=s P \in G_1$ とする。
署名 Sign $(s,m)$ : メッセージ $m$ に対して $σ:=s H_2(m) \in G_2$ を署名とする。
検証 Verify $(pk, m, σ)$ : メッセージ $m$ , 検証鍵 $pk$ , 署名 $σ$ に対して $e(pk, H_2(m)) = e(P, σ)$ が成り立てば受理する。

検証ではペアリングを2回計算してそれを比較しています。ペアリングは重たい計算なので少しでも軽くしたいです。その方法を紹介する前にまずはペアリングの大まかな計算構造を説明します。

ペアリングの構造と署名の高速化第一段階

ペアリングの計算はミラーループML（Miller Loop）と最終べきFE(Final Exponentiation)の部分からなります。

e(P, Q) := FE(ML(P, Q)).

最終べきは、ある定数 $a_0$ を用いた $FE(x) := x^{a_0}$ という形のべき乗計算です。今回は $FE$ の詳細には触れません。ミラーループ $ML$ の詳細は後ほどもう少し触れますが、ペアリングがこの形をしていることを利用してBLS署名の検証アルゴリズムを改善できます。

$FE(x)$ は単なるべき乗の計算なので任意の $x$ , $y$ に対して $FE(xy) = FE(x) FE(y)$ が成り立ちます。
それからペアリングの双線型性から $e(-P, Q) = e(P, Q)^{-1}$ を使うと、

\begin{align*} {} & e(pk, H_2(m)) = e(P, σ)\\ \iff & e(pk, H_2(m)) e(-P, σ) = 1\\ \iff & FE(ML(pk, H_2(m)) FE(ML(-P, σ)) = 1\\ \iff & FE(ML(pk, H_2(m) ML(-P, σ)) = 1. --- ※ \end{align*}

一つ目の同値はペアリングの双線型性、二つ目はペアリングをML+FEに置き換えただけ、三つ目はFEの準同型性によります。
素朴な検証ではペアリング2回、つまりML×2 + FE×2でしたが、※を検証するにはML×2 +FE×1とFEが1個分減ります（ $G_T$ での乗算が1回増えてますがMLなどに比べて無視できるレベル）。
MLとFEの演算コストは1:1.4ぐらいなので、(1+1.4)×2=4.8が1×2+1.4=3.4に減少し、計算時間を約30%削減できました。

ミラーループの構造とマルチミラーループ

ミラーループ $ML(P, Q)$ は $P \in G_1$ , $Q \in G_2$ から $G_T$ の元（正確には $𝔽_p$ の12次拡大体の元）を求める関数です。細かい部分をはしょると次のような形をとっています。

Fp12 ML(G1 P, G2 Q) {
  Fp12 f = 1;
  for (size_t i = 0; i < 定数; i++) {
    f *= f;
    // PとQから決まるある値eを計算
    f *= e;
  }
  return f;
}

前節※の部分では2個MLをそれぞれ計算してから掛けています。しかし、このミラーループの構造を見ると、 $f$ を2乗して $P$ と $Q$ から決まる値を掛けています。
ということは、 $ML(P_1, Q_1) ML(P_2, Q_2)$ を次のようにまとめて計算できます。

Fp12 ML2(G1 P1, G2 Q1, G1 P2, G2 Q2) {
  Fp12 f = 1;
  for (size_t i = 0; i < 定数; i++) {
    f *= f;
    // P1とQ1から決まるある値e1を計算
    f *= e1;
    // P2とQ2から決まるある値e2を計算
    f *= e2;
  }
  return f;
}

MLを個別に計算する場合に比べて $f^2$ の計算回数はループ回数分だけ減らせます。このようなMLをマルチミラーループと（ここだけの用語ですが）呼ぶことにします。
※からの同値を続けると、

\begin{align*} {} & e(pk, H_2(m)) = e(P, σ)\\ \iff & ...\\ \iff & FE(ML(pk, H_2(m) ML(-P, σ)) = 1\\ \iff & FE(ML2(pk, H_2(m), -P, σ)) = 1 \end{align*}

です。mclではmillerLoopVecを提供しています。
2個のペアリングの値が一致することを確認しているコードはisEqualTwoPairingsです。

今回BLS署名のうち、署名が $G_2$ の元となるEthereumタイプの最適化を紹介しましたが、 $G_1$ の元となるDFINITYタイプの場合、ペアリングの引数の一つが生成元 $P_2 \in G_2$ と固定であることを利用して一部の処理を事前計算しておく最適化もしています。

コード中のprecomputedMillerLoop2mixedですが、細部に入りすぎるので今回は止めておきます。

まとめ

今回はBLS署名の検証アルゴリズムの高速化方法を紹介しました。2個のペアリングの値が一致するということを調べるだけでも様々な知識を使って最適化できます。
複数の検証をまとめて行うことで高速化する方法もあります。またの機会に紹介しましょう。

GitHubで編集を提案

初めに

用語の復習

ペアリングの構造と署名の高速化第一段階

ミラーループの構造とマルチミラーループ

まとめ

Discussion