楕円曲線の夢の国に住もう！！
結論：楕円曲線暗号で使えるペアリングは、ゼロ知識証明だけでなく、近年の多くの暗号学的な発明の基盤になっている。
どうも、極度妄想（しなさい）です。
今回は、暗号通貨民にはお馴染みの楕円曲線の住民になるための記事を投稿しました。楕円曲線は色々不思議な性質のある”夢の国”です。
これ以降、初見の人が「マジで！？」って思いそうなポイントは
「(°▽°)<え？マジで？」
を入れます。
さて、ここでこの投稿の目的を先に書いてしまいます。
ペアリングを理解することです。
（少なくとも暗号通貨業界にとっても）最も重要な暗号学的な発明はここ数年、ペアリングが関係しているように思えます。原理と応用の”完全な理解”が目的です。
ペアリングは前述の離散対数問題に根ざした楕円曲線暗号上で使われる機能（性質）です。ではまずは楕円曲線について。
楕円曲線ってなんでしょう？ 楕円曲線、楕円積分（初等数学では計算できない積分）、楕円関数（二重周期関数）は奥で繋がってはいますがそれぞれ全くバラバラのものであり、ネーミングは非常に紛らわしいです。これらはそれぞれ別の分野としてすごく面白いので、別途ググってみると良いでしょう。そして、楕円曲線は、
y²=x³+ax+b
と表現できる全く楕円ではない曲線です。形は下の通り楕円ではない。aとbの組み合わせによっては色々あります。
まぁ浦安ネズミパークではなく東京ディズニーランドというネーミングを受け入れるのと同じな心で、この”楕円曲線”というネーミングを受け入れましょう。
この楕円曲線には不思議な性質があります。この楕円曲線の上の点Pと点Qをある方法で足し算して別の点に移す時、次が成り立ちます。
(°▽°)<え？マジで？
・P + Q = Q + P
P + P = 2Pとすると
・aP + bP = (a+b)P
・a(bP) = b(aP)
簡単に言えば当たり前の性質ということです。
注意して欲しいのは、ここでx倍算を行ってますが、これは何回同じ点を足し算を繰り返すかというのがx であり、点同士の掛け算ではないです。点同士の掛け算というのは楕円曲線にはありません。あるのは整数xを点にかけることだけで、この掛け算は足し算によって構成されています。
で、この点同士の足し算はどのようにやるかと言えば、こんな感じ。
PとQの線を引いて作られた三つ目の点をX軸対象にするだけです。
上図の1と３を見てください。P+Q = -R で、-RはRの逆さまです。
P+Qではなく、同じ点同士のQ + Qの場合は上図2の通り、Qで接線を引きます。
つまり接線を引いて交点をとり、上下逆さまにするのをa回繰り返した点Qがあるとすれば、Q = aPということです。
ここで注意して欲しいのは3番で、線を引いたら真上に行って交点がなくなってしまった場合です。この時、この無限遠方を０として考えます。この足し算における０はこの無限遠点であり、P + 0 = Pです。試してみてください。
こんな操作でa(bP) = b(aP)になるのはとても不思議ですし、この奇跡的に生まれて見つかった足し算の性質を使って様々なことが行えると期待してください。 基本的に制限がなければ楕円曲線上の点Q(x,y)は整数の四則演算の結果なので有理数となります。
このQ = aPにおいて、QからPを求められないことを離散対数問題と言います。
つまりビットコインの秘密鍵はこのaであり、秘密鍵回Pを足した結果が公開鍵Qです。
離散”対数”？対数というより割り算じゃない？って思うかもしれませんが、その疑問を次の章で解決します。
（「プログラミング ビットコイン」は基礎の有限体の概念からECDSA署名までpython実装とともに書いていくところから始まっており、裏切らない知識をつけることに気を使われていて入門には最高の本です。）
群とは、集合に演算がつけられたもののうち、次の性質を満たすものです。
群Gのどの要素 a,b ∈ G 、演算・に対しても1) a・b ∈ G 2) a・e = e・a = aとなる単位元eがある3) a・a’ = a'・a = eとなる逆元a’がある
です。
身近に感じるために、普通の足し算に関して言えば、記号を・から+に書き換えると、単位元を0で、xの逆元が-xになることが分かると思います。
前の楕円曲線上の点の群は、単位元がO（無限遠点）だったということです。
さて、数と足し算が作る群は、無限の数の要素を持ちますが、群は別に限られた数の要素でも大丈夫です。
一つの要素g をg・gを作り、さらにg・g・gという風に作っていって全部の要素を作り尽くせるような群を巡回群といいます。この要素gを生成元といい、全ての要素はg²,g³,g^nのような形に表現できることが分かるかと思います。この肩に乗る累乗の表現は普通の数であれば演算には乗算（掛け算）を想定していると考えて良いでしょう。
ここで重要なのは、群の定義を思い出せば、必ず全ての要素には逆元があるので、g^-1、つまり一回gをかけたら1に戻り、もう一度かけたらgに戻る要素が必ず群内に存在し、g^xのxを増やしていけば必ずこいつにぶち当たるはずです。 巡回する。
オサレに「故に『巡回群』」と言いたいところなんですが、要素は全部gから生成出来ても、無限に要素がある場合は巡回しないですね・・。これは無限巡回群と呼ぶらしいです。無限に巡回し続けるというよりは、無限に巡回しようとし続ける群ですかね。まー、ネーミングは正しい理解で上書きすれば良いのです。
とにかく巡回群の要素の数が無限である場合を忘れれば、巡回するわけです。
g^n = e(単位元)の時、 nを巡回群の位数と言います。つまり巡回群の要素数です。
注意して欲しいのが、要素 x = g^a に関してx^n = eであれば、nはxの位数と呼びます。二つの語用にそれぞれ定義があります。生成元gの位数が巡回群の位数とも言えます。
暗号学の話で出てくるのは、通常の数の演算や普通の集合ではないので、1¹⁰⁰という表現が出ても「は？」と思う前に常識の方を疑いましょう。
これが離散対数問題と呼ばれる背景です。先程の楕円曲線上の加法群では巡回群を作ることができ、Q=aPでしたが これは表記を直せば、Q=P^aでもあったわけで、攻撃者が求めたい秘密鍵 aは a=log_p(Q)です。
そういえば、「群論」というタイトルで群論の話をずっとする本は個人的にあまり見たことがありません。すごくたくさん体（Field）の話をします。体とはなんでしょうか？
体とは演算が二つついており、次の定義を満たします。
体Fとその演算+と演算*に対して、1) 演算+に関してFは群であり、かつ任意の要素a,bに関してa+b = b+aが成り立つ。(これを可換群という)2) 演算＊に関して、Fは+の単位元0を除いたら可換群をなす。0には逆元がない3) 二つの演算*と・の関係として、 分配法則が成り立つ
(a+b)*c = a*c+b*c
c*(a+b) = c*a+c*b
つまり足し算と掛け算が定義された代数構造が欲しいという話であって、それなら体の話がたくさんされても不思議はなさそうです。
にしても複雑ですね。そもそも加法単位元0に乗法逆元がない、つまり0で割れないなんて普通の「数」に無理に合わせてるんじゃないの？もっと簡単にならないの？と思うかもしれません。
しかし、0の乗法逆元zをとりあえず神の視点で作ってみると、
z*0=1z*(0+0) = z*0 = 1
一方、
z*(0+0) = z*0 + z*0 = 2
と不一致となり、分配法則が成り立たなくなります。
あるいは、z*(0+…+0) = n、z*0 = nで全ての数はz*0つまり１に潰れ、0=1になるとも言えます。
ここまで神の視点で世界を作って失敗すると、この宇宙はTwitterとかある分、幾分かマシでしょう。
さて、全ての数が自動でqで割られて余りにされる世界は、それが体になるのであれば、幾分かマシな世界です。
q = 5であれば、
7 ≡ 2
144 ≡ 4にされる世界です。
この世界がなぜマシなのかというと、体になるからです。これを有限体と言います。
(a + b) * c = (b+ a) * c = a*c + b*cなのです。
そして０以外には乗法逆元があります。
基本的にqとaが互いに素なら必ずa*b ≡ 1となるbが（q未満に）存在します。つまり、qが少なくとも素数である時はこの世界の元は逆元を持ち、体になります。
「体になるなんて当たり前」とか思ってません？整数は体にはなりませんよ。乗法逆元がないですから。有理数は体になります。
さて、乗法逆元を求めるというのはつまり、割り算をするということになります。
a *b = 3なら
b = 3÷a = 3 * 1/aです。
つまりb = a-¹ * 3なので、aの逆元と3を掛け算してやれば、bを割り算として算出できます。
ではこの有限体 において逆元はどうやって求めるのでしょう？この計算を逆モジュラー計算と呼びます。
(°▽°)<え？マジで？
ここでですが、 a^q ≡ a (mod q) です。
これはフェルマーの小定理と呼ばれてフェルマーの大定理(フェルマーの最終定理)より全然有名でよく使われる定理です。このネーミングもまーいいんですよ、多分。
厳密でなく フェルマーの小定理 a^q ≡ a (mod q) を簡単に説明すると、
1) qは素数なので、{a,2a,3a,…,(q-1)a}の集合の要素全てと互いに素である。2) そしてこの集合の各要素をqで割って生まれた集合は{1,2…..q-1}と一致する。全部の要素を掛け合わせると、
a*2a*3a*..*(q-1)a ≡ 1*2*3…*(q-1)よって、a^(q-1) ≡ 1
ってことは、a^(q-2) * a ≡ 1 なので、a^(q-2)がaの乗法逆元ですね。
これにより、有限体の逆元はすぐに求まります。つまり、有限体上で割り算をする時は、q-2乗する計算が入ることになります。経験則としてなんとなく染み付いてるのは、ナントカ乗計算とか再帰的導出とかは大体log(N)オーダーの計算量で実行が可能です。
(°▽°)<え？マジで？
しかしながら、a^p ≡ x (mod q)で、aとxが明らかな時でも、pは求めることが出来ません。これを有限体上の離散対数問題と言います。
とりあえず言いたいのは、この全ての数が素数qで割られた余りに一々変換される世界の有限体を今後はずっと使っていきます。
有限体上の楕円曲線とはなんでしょうか？
最初に楕円曲線の話をしたときに、「点Pをa倍してQを作るときに、Q = aPからaは求まらない(楕円曲線上の離散対数問題)から、aを秘密鍵にできる」という話をしたと思いますが、楕円曲線はy² = x³ + なんちゃら なわけで、点Q(x,y)が巨大になってしまうと問題です。なので(x,y)を有限体Fq上にトレースすることとします。
つまり加算演算を作る際の、接線を引いたり(x,y)を求めたりする操作が含んだ導出式も、全ての計算結果をqで割ることにします。これにより、下の図のような全ての有理点はバラバラになり、q × qの正方形の中に散りばめられることになります。
(°▽°)<え？マジで？
驚いたことに、全部有限体の標数qで全てを割っても、元の普通の有理数でやってた楕円曲線上の操作で一致する計算は全て一致するんですよね。
接線の傾きが有理数体上では分数になりますが、有限体上ではさっきの乗法逆元を使った割り算された数が”傾き”になります。
y² = x³+ax+b上でP(x1,x2)を２倍算(P+P)して(x4,y4)にするときは、最終的に以下のような計算式になりますが
この全ての計算を素数qで割り、分数の部分は逆モジュラー計算にし、出力の(x,y)を有限体上の点とします。つまり分数は消えました。
お察しの通り、楕円曲線暗号とか言いますが、有限体上だとqで割られて全ての数がバラバラに移され、点もあっちこっち散らばってしまうので、全然直線とか曲線とかないです。
楕円曲線暗号は、楕円ではない楕円曲線が素数で割られてバラバラに散ったものの上で動いています。ズレすぎてても成り立つと逆に感動する現象にまで突入。
いずれにせよ、素数qで全てを割れば、楕円曲線で生まれた綺麗な加法の性質は全て保存されるということです。
さて、公開鍵・秘密鍵をコンパクトにすることには成功しましたが、実際にどうやって、この鍵を使って暗号化したり、電子署名をしてビットコインを動かすのでしょうか？
暗号化は比較的簡単です。
a(bP) = b(aP) なので、Pが共通で知られていて、公開鍵A = aP、公開鍵 B = bP が知られているのであれば、Aの秘密鍵a保有者はBの公開鍵Bに対して K = aBします。
Bの秘密鍵b保有者はAの公開鍵Aに対して K = bAします。すると、この２人以外には誰にも知られない共通鍵Kを平文に加算して暗号化できます。
この鍵配送と言われる工程ですが、bが一時的な使い捨ての鍵として扱うと「楕円曲線エルガマル暗号」となります。
ビットコインでもお馴染みのECDSAを速攻で攻略！
次のECDSA署名はパッと見だと複雑ですが、分解すると余裕です。
まずは複雑な形式的手順を見ます。
・署名者は、公開鍵Aと秘密鍵aを持っています。ハッシュ後のメッセージmに対して署名がしたいです。ベースポイントの点Pや素数lという情報も皆知っています。1)有理数体Fl上のランダムな数kを使って、K = kP = (x,y)を作ります。2)署名をFl上の数 s = k^-1 * (h + ax) とする・検証者は公開情報 h,K,Aから署名sを次のように検証する（ECDSAの実際の実装との差異は後述）Fl上の数、uとvを次のように計算するu = s^-1 * h
v = s^-1 * xuP + vAがKと一致したらOK！
なぜなら、
uP + vA
= (s^-1*h*P) + (s^-1*x*a*P)
=s^-1*(h+ax)*P
=k *(h+ax)^-1*(h+ax)*P
=K
「だから！大丈夫！」と言われてもこれはなかなか初見だと難しいです。
分解していきましょう！
これは一度数学でも暗号学でもなく、作者の気持ちを考える小学校の国語の授業だと思って考えてみます。
では0からECDSAを作る人の気持ちになりたいので、セキュリティ的にめちゃくちゃですが、署名sを s = (h+a) でやってみましょう。x = 1、k = 1です。これが1番シンプルバージョンです。
・検証者
s = (h+a)を受け取りu = s-¹ * h
v = s-¹uP + vA
= (s^-1*h*P) + (s^-1*a*P)
=s^-1*(h+a)*P
=(h+a)^-1*(h+a)*P
=P
ベースポイントに戻ってきました！k = 1なのでK = Pであり、成功です！
これじゃダメなの？
余裕でダメです。s = h+aがバレてるので秘密鍵aがバレます。
なのでランダムな数kを使ってs = k^-1*(h+a)にしてバレないようにしましょう。検証側ではkが入ったs^-1が掛かることにより帳尻を合わせます。
検証者 s = k^-1*(h+a)を受け取りu = s^-1 * h
v = s^-1 検証
uP + vA
= (s^-1*h*P) + (s^-1*a*P)
=s^-1*(h+a)*P
=k *(h+a)^-1*(h+a)*P
=K
これで、Kに戻ってこれたので、大丈夫！！ってことはECDSAのh+axのxって要らなくない？
なんか、ぱっと見はそう思えてしまいます。しかしながら、これは確かに秘密鍵がバレたりすることはないのですが、署名を偽造することが可能になってしまいます。
攻撃は以下の通りです。
偽造署名
K = hP+A
s = 1
は上の検証手順を通ってしまいます。uP + vAに合うようにKを後から作れば良くなってしまうのが問題ですね。ちなみにsは任意のnにしても n^-1をKに乗算していくらでも調節できるので、s=1を外すのは偽造の対策になり得ません。
というわけで
s = k^-1 * (h + ax)
が必要です。
以上で、ECDSAの手順と各計算の意味を追い終わりました。
(°▽°)<え？マジで？
ちなみに最後に超重要事項ですが、このランダム値kは知られたら秘密鍵aが導出されバレてしまいます。（上の式変形で簡単に計算できるのでお試しを）
さらに言えば、k自体が知られてなくても、同じkが使われてると分かっている二組の署名sがあればkが導出されaも導出されます。
kは必ずランダムに生んで破棄する必要があります。
kはナンスとか適当なランダム値とかネーミングされてますが、プチ秘密鍵みたいなもんです。
ここまでで、一般的な楕円曲線暗号の教養的な理解は終わりましたし、多くで使われているのはここまでの範囲かなと思います。
ここからはおそらく専門的な内容なんだろうと思いますが、最後まで赤い四角形が赤くなるまで付き合ってくださると、動機はないですが、割と嬉しいです。
これからは、この楕円曲線に「著しい性質」をつけていきます。
x²-2= 0 の答えは有理数ではないですね？
この答え√2を有理数体Qに特別に加えたらどうなるでしょう？
体として加法演算・乗法演算に関して閉じなければならないので、√2 + 3とかもこの拡大した体Q（√2）の中に入ります。一般的に、a + b√2であり、(a,b)の2次ベクトルで表現することもできますね。乗法に関しても２次ベクトルで閉じます。
これが、有理数体Qではなく、有限体Fp上だったらどうでしょう？
例えばp = 5の時、x²-2=0の解αをFpに特別に加えるとき、Qの時のように具体的に記号を設けて√2のように解を求めることはしないです。何故なら、Fq上の方程式の存在しない解は、√2と違って本当に存在しない数なので。ジャンルとしては虚数に近いですね。
しかし、a + bαの中で閉じると考えれば、0≤ a,b ≤4 なので、有限体は25個の元を持つ体に拡大されました。
これがx³-2=0の解を加えて拡大するときは、拡大された体のベクトルは３次になります。つまり、定義となる既約な多項式の次数だけ体の次元は拡大されます。余りの多項式が2次になるためです。
この拡大された体を「有限体の拡大体」と呼び、有限体F_pのm-1個の新しい元を追加した場合、F_ p^mと書きます。このmを拡大体の次数と呼びます。
有限体F_2上の既約多項式x⁴+x+1の解αを加えて、F_2を拡大してみましょう。画像は今回はたまたまαが原始元（生成元）になって巡回が作れるので、以下のように要素を全てαの累乗で表せています。
出典資料自体がとてもわかりやすいのでおすすめです。
さて、有限体の最も特徴的な性質としてフロベニウス写像の存在が挙げられます。
フロベニウス写像 σは有限体の標数をqとすると σ(x) = x^q と定義されます。
フェルマーの小定理 x^(q-1) % q=1を覚えてる人からすれば、x^q % q= xなので「は？恒等写像じゃん！」と思うでしょう。
言い換えると、有限体は乗法に関しては0を抜くと位数はq-1になる巡回群になるすれば、「巡回群上の元Pは位数回P同士を演算すれば単位元に戻る」と考えられます。
gを生成元としてP = g^p だとするとき、P・…・P=(g^p)^q = eということです。g^q = eなので当たり前と言えば当たり前なのですが。
この「巡回群上の元Pは位数回P同士を演算すれば単位元に戻る」という性質を「オイラーの小定理の一般化」と言います。
つまりビットコインなどで使われる有限体上の楕円曲線上の巡回群において、その位数を#E[F_q]とすると、任意の点Pに対して、
Q = #E[Fq]*P = O
です。
ここで、いきなり 1-t+q = #E[Fq] とおくと、
もちろん、
1*P -t*P +q*P = O
そして有限体上では恒等写像になるσを使って、
σ(P) -t*σ(P) + q*P = O
σ²(P) -t*σ(P) + q*P = O
です。
有限体上では当たり前のことしかしてませんが、この方程式はフロベニウス写像の特性多項式と言われ、次の「著しい性質」持ちます。
(°▽°)<え？マジで？
標数qを固定した上で、その拡大体 F q^m に関しても、
σ²(P) -t*σ(P) + q*P = Oが成り立ちます。
拡大体上で新しく加わった元に対してはσは恒等写像にはならないのにも関わらず！！（逆に拡大前からいた元には恒等写像です）
σが恒等写像にならないことは次から明らかです。
フロベニウス写像が恒等写像になる場合、x^q -x = 0を満たす必要がありますが、この多項式の根は拡大体だろうが、絶対にq個以上になりません。拡大体の位数q²なので、大量の元があぶれます。
証明は難しいので省きますが、このフロベニウス特性多項式により、拡大体上の楕円曲線群においても、全ての点を無限遠点に変換する方法を見つけることができました。
次に拡大体上の楕円曲線の話である、楕円曲線上の等分点・ねじれ点の話をしようかなと思います。
普通に考えれば、ただの有限体上の楕円曲線で、ビットコインやイーサリアムなどで現実に使える楕円曲線暗号はできてしまっているので、わざわざ拡大体上で楕円曲線について考える意味がないかもしれません。
しかし、この先にはペアリングが待っており、ペアリングの先にはzkSNARKsやKate commitmentといったVerifiable Databaseの世界、Ethereum2.0やEthereum Layer2 zkRollupなどの次世代型ブロックチェーンの世界が広がっています
後で出てくる「ペアリング」には等分点と呼ばれる点を探す必要があります。
m等分点は mP = O となるような点Pです。
ん？それは普通の楕円曲線でもあるだろ！って思うでしょうが、そういう点もありうるし、mによっては等分点が有限体上に見つからない場合があります。その時、楕円曲線で使われている定義体を拡大することで等分点をこじつけます。
このm等分点P(x,y)の求め方ですが、
等分多項式φm(x)=0となればOKです。
ではそのφmの求め方ですが、漸化式的に求まります。
楕円曲線をy² = x³ + ax + bとします。
以下例題を辻井先生・笠原先生著の「楕円曲線と暗号理論 」から借りますと、
例えば、有限体F5上のy²=x³+x+1の３等分点は、
φ3 = 3x⁴+x²+2x+1=3(x-1)(x-2)(x²+3x+4)
となり、
x座標は上の式の根となります。
x³+3x+4の根は有限体上にないため拡大して作ります。
最小多項式と言ってF5²に拡大するためにその根を加える方程式の中で、最小次数で、最初の項の係数が１となるものを選びます。
F5²ですと、X²+4X+2です。
この根をαとすると、計算は大変ですが、x = α²とα¹⁰がx²+3x+4の根となるので、この4つのx座標から生まれる8つの楕円曲線上の点は等分点となります。
あと、無限遠点Oはm倍したら当然Oに行くので等分点です。
ねじれ点とは、このm等分点となる点P,Qが２つあるとすると、
R = aP+ bQ は必ず等分点ですね？
mR = maP+mbQ = amP+bmQ = aO+bO = Oですから。
そうすると、このm未満aとbを使って全ての点がm等分点になる格子が作れます。この格子状の点Rをねじれ点といい、この格子をねじれ点群と言います。
そろそろペアリング、ペアリングと中身も言わずに沢山言われてイライラしてたりしますかね？
では先にどんなものなのか、説明しましょう。
定義体をFとして、n等分点から作ったnねじれ群をE[n]としますと、ヴェイユペアリングenは
en: E[n] × E[n] -> (Fの拡大)
です。
ねじれ点二つからFの拡大上の数を出力します。この(Fの拡大)はねじれ点を作るために作った拡大体よりさらに大きく拡大されており、代数閉包と呼ばれるものです。簡単に言えば全部の多項式の根が足されたものです。
ヴェイユペアリングenには著しい性質があります。
(1)双線型性
en(P1+P2,Q) = en(P1,Q)en(P2,Q)
en(P,Q1+Q2) = en(P,Q1)en(P,Q2)付随的に en(aP,Q) = en(P,Q)^a付随的に en(P,O) = en(O,Q) = 1
なぜならen(P+O,Q)=en(P,Q)en(O,Q)、en(P,O+Q)=en(P,Q)en(P,O)(2)非退化
P!=O ならば、en(P,Q) != 1となるQが存在する=====================
ここまでは、これから出てくるテイトペアリングと共通の性質以下はヴェイユペアリング特有の性質(3)同一性
en(P,P) = 1故に
1 = en(P+Q,P+Q) = en(P,P)en(Q,Q)en(P,Q)en(Q,P)en(P,Q)en(Q,P) = 1
特にen(aP,Q) = en(P,Q)^aでは楕円曲線上の点の倍算が、拡大体上の累乗計算に結びついていることがわかります。
これでとりあえず、一つECDSAとは全く違い、遥かにシンプルな署名システムが作れます。
BLS署名です。
署名者： 公開鍵Q2と秘密鍵aを持っており、Q2= aQ。メッセージmに以下のように署名する。（Qは公開パラメータですがベースポイントではないです。）署名s = a*m ∈ E[n]検証者：en(s,Q) = en(m,Q2) になるか確認なぜならen(s,Q)=en(am,Q)=en(m,aQ)
(°▽°)<え？マジで？
以上です。危険なランダム値（ナンス）であったk値がないのでECDSAより安全とも言えます。ペアリングの計算量が大きいですが。
基本的にこのペアリングの計算と検証において楕円曲線暗号で使われていた離散対数問題の安全性がそのまま引き継がれたまま双線型性が加わったので、「何かを見せずに証明する」というのが色々書きやすくなっています。
さて、（Fの拡大）とかいた代数閉包になるまで拡大する際に次数がいくらになる、つまりFq^dをいくらになるまで拡大する必要があるかは場合によって違います。一般的なペアリングの実装ではd=12になっており、つまり12次元のベルトルになります。これがペアリングの計算が少し重い理由です。d=6とかになってしまうとMOV攻撃と言われる攻撃を受けてしまうのでそうならない曲線を選びます。こう言った理由から。基本的には超特異曲線と呼ばれる曲線は暗号には使わないようにしています。また特異曲線ももっと深刻なセキュリティ上の理由から使われません。
具体的にどのようにenを作れば良いのでしょうか？
ここはペアリング計算の速度を気にする人のみが読めばいいです。辛くなったら次の章に飛んでください。
まず、楕円曲線上の点Pに形式和(P)という概念を入れます。
例えば 楕円曲線上でP+Q=P2の時、
3(P) + 3(Q) != 3(P2)
であり、
3(P) + 2(P) = 5(P)です。
イメージ的には一つ一つの楕円曲線上の点が独立の基底ベクトルみたいな感じです。
ただ注意して欲しいのは、今嘘をついたところでして、楕円曲線上の点というよりは先程の(Fの拡大）と書いた代数閉包まで拡大したFの拡大上の楕円曲線です。
この形式和で表せるものを因子(divisor)と呼びます。
D= 3(P) + 2(Q) とかです。
楕円曲線上の有理関数f に対しても因子を 定義することができ、
P = (x,y)
分母関数： g(P) = g(x,y)
分子関数： h(P) = h(x,y)
で f =h(x,y)/g(x,y)で点ではない数を出力するとしますと、
fの因子div(f) = Dは
D = Σ n_i(P_i)
です。
ここでP_i はどういう点を列挙してきたかというと、g(x,y)のゼロ点とh(x,y)のゼロ点の集まりです。つまりfが無限に飛んだり、ゼロになったりする点です。
n_iはそれぞれのゼロ点(解)における重解度ですね。(x-2)³であれば2における重複度n_iは３です。分母関数の場合にはこれにマイナスがかかります。
因子Dでも関数因子div(f)でもいいですが、このDに対して次の２つを定義します。
1) Dの次数 deg(D) = Σ n_i
つまり重複度の合計です。
2) Dの関数φ(D) = Σ n_i *P_i
これは Σ n_i(P_i) でD自体が表されていたことを思い出すと、いきなり形式和をやめて、()をとり、楕円曲線の倍算・加算を始めたイメージです。
簡単に言えば「実際に計算してみた」
さて、ここでアーベル＝ヤコビの定理を紹介します。
(°▽°)<え？マジで？
「ある因子Dが有理関数fの因子であるための必要十分条件はdeg(D)=0,φ(D)=0」
これは何を言っているのかというと、まず、
- (代数閉包上の)楕円曲線と他の任意の有理関数との交点を重複度込みで全部足すと無限遠点Oに飛ぶと言っています。
2. そして、逆に、足したら無限遠点Oになるような点の組み合わせからは、そこを楕円曲線との交点とする有理関数が必ず作れる
と言っています。著しい性質です。
1については、この有理関数fが１次関数、つまりは直線である場合上の話は自明です。なぜなら楕円曲線上の点が１つの直線にのる場合はそれらを足したらOなのですから。有理関数は結局は１次関数の掛け算と割り算で構成されることがこの性質を作っています。
これら２つはあまりにも著しい性質であるため、何かに使えることは間違い無いでしょう。ではヴェイユペアリングenを具体的に構築していきます。
その前に一つだけ、点を入れるはずの有理関数fに因子Dを入れること定義しますと、
f(D) = Πf(P)^n_P
つまり、fに因子に入ってる点Pを代入していき、それぞれ重複度を累乗します。それを乗算で掛け合わせます。
さて、ヴェイユペアリングen(P,Q)をnねじれ点の上で作りたいです。
P,Qから因子D_PとD_Qを一定の法則で生成します。
その条件は φ(D_P) = P で、φ(D_Q) = Qです。
これはアーベル＝ヤコビからすると有理関数の因子ではないものです。しかし、nD_PとnD_Qはφ(nD_P)= nP = O なのでアーベルヤコビを満たし、なんかの関数の因子になります。nD_PやnD_Qはこれから作る関数f_Pとf_Qの因子としましょう。
div(f_P) = nD_P
div(f_Q) = nD_Q
ここで、
en(P,Q) = f_P(D_Q) / f_Q(D_P)
としてみましょう。
すると、ここで有理関数同士の掛け算f_P1・f_Pについて、
div(f_P1・f_P2) の内容はdiv(g1/h1*g2/h2) であり、f_P1とf_P2は因子について線形に計算できるので、div(f_P1・f_P2) = nD1 + nD2となる。
D_(P1+P2) = D_P1 + D_P2
故に f_(P1+P2) = f_P1・f_P2
条件が揃ったので双線型性を確認していくと、
en(P1+P2,Q)
= f_(P1+P2) (D_Q) / f_Q(D_P1+D_P2)
= f_ P1(D_Q) /f _Q(D_P1) * f_P2(D_Q) / f_Q(D_P2)
※ここは上の条件を使えば導けます。
= en(P1,Q) * en(P2,Q)
なんかやっとできた〜って感じしますが、具体的にD_Pからf_Pを計算する方法がまだです。
ここにはミラーのアルゴリズムというものを使います。
ここからダウンロードして18章7節を見て頂くと、具体的に逐次計算する方法が載ってます。
https://github.com/herumi/ango/blob/master/ango.pdf
お馴染みの累乗計算は二進展開することでlog(N)オーダーになるパターンらしく、著者のherumi先生が世界最速のライブラリ実装者となってDFINITYなどで使われていたそう。
テイトペアリングは、ヴェイユペアリングのf_P(D_Q) / f_Q(D_P) の分母分子で2回ミラーのアルゴリズムを回していたのを1回で済ませる手法です。なので速いです。
ちょっと省略して書きますが、
en: E(Fp) × E[n] -> (Fの拡大)
です。
ヴェイユペアリングの
en: E[n] × E[n] -> (Fの拡大)
と違い、片方は拡大体上のねじれ点ではなく、楕円曲線上の点であり、拡大してないので1次元です。
目的としては、en をヴェイユペアリングのように、f_P(D_Q) / f_Q(D_P)ではなく、f_P(D_Q)だけで終わらせたいのですが、基本的に、div(f_P) = nD_Pである点、div(f_Q) = nD_Qであるまでは同じ出発点です。
ここでgの因子をdiv(g) = (P+Q) -(P) -(Q)としてみると、
div(f_P*f_Q*g^n) は前のdiv(f_P1・f_P2) = nD1 + nD2の時と同じ要領で
n (P)+ n (Q) +n (P + Q)-n (P)-n (Q) = n(P+Q)となり、これにより
div(f_P*f_Q*g^n) = div(f_P+Q)
になりました。分子だけで終わってくれましたが、残念ながらg^nという余計なものがついてきたので、これを殺します。
gもg^nもFq¹²の中に入っている要素なので、フェルマーの小定理の一般化から、g^(q¹²-1)を行いnで割れば必ず１になります。
これにより、最後にこの計算を入れることで、
f_P* f_Q = f_(P+Q)の性質を持つ関数を導入することが可能になります。
ここにフォーカスしたブログとしてはVitalikのものが分かりやすいので置いておきます。
https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
最後までとうとう来てしまいました。
途中からつまらない冗談すら言わなくなったので僕の方にも余裕がないことが伝わったのではないでしょうか？笑
もう、ここまで読むと普通にクリプト（仮想通貨）業界の先端の論文は読めるようになります。楕円曲線の住人です。もう自由に泳いで下さい。
ではペアリングを用いてBLS署名以外のケースも紹介してみます。
これはアルゴランドのチームが出したpointproofsの論文でアルゴリズムの雛形として紹介しているLibert & Yungのベクトルコミットメントです。
ここで、最後の1行が一致することをペアリングの定義式を使って一行一行追うと確認できます。
これの何がいいかと言えば、マークルプルーフの上位互換を作ろうとしているんですね。マークルプルーフは以下のように、不可逆ハッシュを二個ずつ繰り返すことにより、1個のRootコミットメントにまとめてしまい、そのコミットメントに対して1番下の葉っぱがRootに”含まれていること”を証明します。ビットコインを構成する重要な部分です。
この緑の部分を証明するためには青いデータを持っていれば、それを順繰りにハッシュしてRootが復元できます。proofのサイズは下の持っておきたいデータの数N（この図だと16）に対して,log(N)に収まります。非常に効率的。
このようなデータベースをVerifiable Databaseと呼びます。「ブロックチェーン業界」はVD業界とかマークルツリー業界とか名乗ってもいいとは思いますよ。IT外には分かりにくくなりますが、ITの内では通じやすくなるかも笑
しかし、このハッシュ計算やlog(N)にまだ強い不満を持ちさらに飛躍的に効率化したいという派閥があります。それがこのPointproofsやKate commitmentです。これらような多項式コミットメントと言われる手法はEthereum2.0に使われる予定です。基本的な技術はペアリングです。
ペアリングは他にzkSNARKsなどにも使われています。
この解説は、僕の大学の友人の河合くんの解説が個人的には1番わかりやすいです。これを一行一行丁寧に式を追うのがよかったと記憶しています。
https://medium.com/@souiti488/explaining-snarks%E3%81%AE%E8%A7%A3%E8%AA%AC-b1bce7b04c2f
Author：極度妄想（しなさい）
多分このままこう進んでいけば行けば社会は暗号や数学で作られていくことになるんだと思います。多分自然とインターネット上のルールやコードが今の社会を超越していくのだと思います。楽観的で諦観的で熱狂的な楕円曲線住民が増えると割と嬉しいです。
