Develop with pleasure!

福岡でCloudとかBlockchainとか。

楕円曲線の点に対する部分群のメンバーシップチェック

Cryptography ECC

先日Besuに存在していたBN254曲線上の点の検証ロジックのバグが開示された↓

blog.ethereum.org

このバグの内容とは直接関係ないけど*1、解説の中に登場していた楕円曲線上の点が部分群に属しているかどうかのメンバーシップチェックの方法がいろいろあるようだったので調べてみた。

※ Bitcoinが使用しているsecp256k1のように位数が素数で構成される楕円曲線は曲線のサブセットとなる部分群を形成しない（cofactor = 1）ため、このメンバーシップチェックは不要。一方、部分群を構成する楕円曲線を使用している場合に、点の有効性は、その曲線を使用する楕円曲線暗号で使用している有効な部分群に点が属しているかのチェックが必要になる。このチェックが抜けていると脆弱性が生まれる↓

techmedia-think.hatenablog.com

素数位数の乗算

楕円曲線の位数（＝楕円曲線上の点の総数）をnとし、nが素数でない場合、その楕円曲線は部分群を持つ。楕円曲線暗号の各演算は安全性の観点から、非素数位数nの楕円曲線ではなく、素数位数（lとする）を持つ部分群上で行うことが推奨されている。cofactorは、曲線の位数nと主要な部分群の位数lの比率で、h = n/lで計算される。

部分群に属するかチェックする簡単な方法は、点Pに素数位数lを乗算し、l * Pが無限遠点となるかどうかチェックする。素数位数の群の任意の点に位数を乗算すると必ず無限遠点となるため、l * Pが無限遠点と等しければPは正しい部分群に属している。↑のMoneroの脆弱性の対応でも、この方法のチェックが追加された。

ただ、素数位数は大きな値になるため、l * Pの計算はコスト高になる。秘密鍵から公開鍵を計算する際のスカラー倍算と同じコストでは？と思ったけど、公開鍵や署名の計算は固定の点Gに対して行なわれるため、Gに対して様々な倍数（2G, 4G, 8G, ...）を計算した事前計算テーブルを用意しておくことで、計算処理の最適化が行える（Bitcoinのlibsecp256k1の実装でも採用されている）。

また、特にBN254やBLS12-381の {G_2}群での計算は拡大体 {\mathbb F_{p^{2}}}上の計算となるため、secp256k1曲線のような有限体 {\mathbb F_p}上の計算に比べて計算コストが約3〜4倍かかる。

自己準同型写像を利用したチェック

Michael ScottやYu Daiらによって提案されたのが、自己準同型写像を使ってメンバーシップチェックを高速化する手法。楕円曲線上の自己準同型写像は、ある楕円曲線Eから同じ楕円曲線Eへの写像 {\phi : E \rightarrow E}で、以下の性質を持つ。

  • {\phi(P + Q) = \phi(P) + \phi(Q)}
  • {\phi(\infty) = \infty}

用途は違うけど、GLV法なんかも自己準同型写像を使ってスカラー乗算を高速化している。

最初にScottが提案したBLS12-381の部分群のメンバーシップチェックを高速化する手法では、フロベニウス写像を用いる。有限体 {\mathbb F_q}上の楕円曲線のフロベニウス写像は、

{\phi(x, y) = (x^{q}, y^{q})}

と定義され、点の座標をq乗した座標になる。そしてこのフロベニウス自己準同型写像は、以下の特性多項式を持つ。

{\phi^{2} - t \phi + q = 0}

ここで、tはトレースと呼ばれる値で、有限体の位数q + 1から曲線の位数を引いた値↓

{t = q + 1 - \sharp E(\mathbb F_{q})}

↑の特性多項式を性質を利用して、点Pに対して、

{\phi^{2}(P) - t \phi(P) + qP = \infty}

が成立するかチェックということみたい。 {qP}は正確には {(q \mod l) P}でBLS12曲線の場合 {q \mod l = 1}となるので、正確には、 {\phi^{2}(P) - t \phi(P) + P = \infty}を計算することになる。

この場合、スカラー乗算が登場するのは {t \phi(P)}の部分だけで、残りはフロベニウス写像の計算（スカラー乗算に比べて計算コストはかなり低い）と、点の加算のみ。ここでtの値が、素数位数lの値よりも小さいため、上記の検証した方が速度が速くなると。

その後、Daiらによって他の曲線でも使えるように、検証する式が、

{c\phi^{2}(P) - b \phi(P) + aP = \infty}

という形式に一般化されたらしい。a, b, cは曲線毎に設定される。

Tateペアリングを利用したチェック

Tateペアリングを利用する手法はDmitrii Koshelevによる提案で、↑の自己準同型写像を使用するチェックの方が高速な一方、ペアリングに適していない曲線にも適用できるのが特徴。ペアリングに適していない曲線でペアリングを使って検証というのは不思議に思うけど、完全なペアリング計算の結果（e（P, Q）の値）が必要な訳ではなく、ペアリングの特性（ {e(P, Q) \neq 1}を判定できればいい）を部分的に利用しているということみたい。ペアリングについては、以前の記事参照。

この手法は、eをTateペアリングとした場合、点Pに対して適切に選択した点Qに対してe(P, Q) = 1が成立するか検証するというもの。Qの選択方法とか、個人的にこの辺りの背景はまだよく理解していない。

*1:バグの内容は楕円曲線の点について、有効な部分群のメンバーシップチェックはしていたけど、楕円曲線上の点かどうかのチェックをしていなかったというもの。