j-不変量0の楕円曲線の点圧縮アルゴリズムを改善する論文の紹介

Table of Contents

本稿では、この論文を扱います。
https://eprint.iacr.org/2020/010.pdf

この記事で紹介する内容

楕円曲線暗号の多くのプロトコル(ペアリングなど)で用いられる標数 $p$ の有限体 $F_q$ 上のj-不変量が0の楕円曲線上の点を圧縮する「二重点圧縮」の簡単な式を得る方法。
この際用いられる楕円曲線は $E_b: y^2 = x^3 + b$ で表される。ここで $b ∈ F^{*}_q$ である。
そもそもbitcoinで使われているsecp256k1の圧縮公開鍵のサイズを見れば分かるように本来楕円曲線上の点Pのx座標だけを保存しておく（圧縮）ことで本来の楕円曲線上の点Pを回復（復元）することができる。本稿の圧縮方式であっても圧縮後のサイズは変わらない。
しかし、本論文によれば、2つの点をまとめて圧縮する際のアルゴリズムを工夫することで点を個別に復元する際の計算量よりも少ない計算量で同じ復元が行えることになる。
なお下記のテーブルの通り、圧縮時の計算量はむしろ2回のinvmod操作が必要なため増えていることに注意せよ。
復元時に必要なべき乗算(exp)の削減が、それを上回る効用をもたらす場合にのみ本論文は意味がある。

この二重点圧縮の特徴

要素 $Ｚ \in F_q$ の-6乗を扱う。

これは $q \equiv 3 \ (mod\ 4), q \not\equiv 1\ (mod\ 27)$ のとき $F_q$ での指数化が一回のみでできるということを利用するためである。
古典的な方法であると二回必要。

二重点圧縮

ここで、 $n \in Z/6$ は、要素 $z:= x_1y_1 \in F_q$ の位置番号である。

条件 $\phi_k(P_0) = P_1$ は、同型写像 $\phi$ が $F_q$ 上に定義されている場合、つまり $β^{-6} \in F_q$ が成り立つ場合である。

二重点の復元

アルゴリズムを追うと復元時の計算量がナイーブに計算した場合より少ないことが分かる。

圧縮テクニックの拡張

他の楕円曲線の形式であっても有効な場合がある。

$E_a : y^2 = x^3 + ax$ ,j-不変量1728, $q \equiv 1\ (mod\ 4)$
の場合でも次数4の $F_q$ 同型写像が $E_a$ 上に存在するため、この圧縮テクニックは使用可能である。

この論文で話題になっている楕円曲線( $E_b: y^2 = x^3 + b$ )にはビットコインで使われているsecp256k1も当てはまります( $b = 7$ )。
ビットコインの場合楕円曲線上の点の圧縮を行うのは主にアドレス作成時のユーザーであり、検証を行うのは全フルノードクライアントであるため一見この方法が有効そうですが、ユーザーが２つの公開鍵を同時に用意するというシチュエーションが中々無さそうです。
もしもマイナーがブロックを生成するタイミングでトランザクションに含まれる全ての公開鍵をこの方式で圧縮するような仕組みができれば、フルノードの検証速度が向上するメリットはありそうなので、署名検証のバッチ化の一つの案として考えておくのは良さそうだと思いました。