楕円曲線ペアリングの探索

著者：Vitalik Buterin

原題：《Exploring Elliptic Curve Pairings》

発表日：2017年1月14日

暗号学の多くの基盤技術、例えば「決定的閾値署名」（deterministic threshold signature、仮訳）、zk-SNARKsや他の形式の比較的単純なゼロ知識証明などの背後にある重要な原始モデルの一つが楕円曲線ペアリングです。楕円曲線は30年以上にわたり、暗号、デジタル署名などの暗号学的応用に広く使用されており、「楕円曲線ペアリング（EC pairings）」（または双線形写像）は最近その上に基づいて登場した新しい技術で、暗号的乗算を導入し、楕円曲線に基づく合意でできることが大幅に増加しました。この記事では、楕円曲線ペアリングを詳細に紹介し、それがどのように機能するかを簡単に説明します。

この概念は本当に理解しにくいものであり、あなたが最初の一回、あるいは十回読んでも完全に理解できるとは期待していませんが、この記事が少なくともその奥深さのいくつかを教えてくれることを願っています。

楕円曲線自体は理解しにくいテーマですが、この記事では大部分の時間、あなたがその動作原理についてある程度の理解を持っていると仮定します。もし基本的な概念がない場合は、入門としてこの記事をお勧めします。一般的に、楕円曲線は「点（points）」と呼ばれる数学的オブジェクトを扱い、簡単に言えば二次元平面上の点（x, y）や、特別な加減算の公式（例えばR = P + Qの計算）を使用します。また、点を整数で乗算することもできます（例えばP * n = P + P + … + P、ただしnが非常に大きい場合はもっと速いアルゴリズムがあります）。

これは点の加法が図でどのように見えるかです

そのほかに「無限遠点」（O）と呼ばれる特別な点があり、点の演算規則において零要素として機能します。つまり、すべての点に対してP + O = Pが成り立ちます。曲線は「階（order）」と呼ばれる特性を持ち、すべてのPに対してP * n = Oとなる正の整数nが存在します（もちろんP * (n + 1) = P、P * ((7*n) + 5) = P * 5、という具合です）。また、事前に合意された「生成点（generator point）G」があり、これは加法の単位要素として選ばれ、数字1を表す役割を果たす点です。理論的には、任意の曲線上の点が生成元として使用できますが、重要なのはそのGが統一的に選定されていることです。

ペアリングは、特定のより複雑な等式を検証することをさらに可能にします。例えば、もしP = G * p、Q = G * q、R = G * rであるとき、p * q = rが成り立つかどうかを確認するには、P、Q、Rの3つの点の座標を入力すればよいのです。これは一見、楕円曲線の最も基本的な安全保証が破られたように見えるかもしれません。なぜなら、P点の座標を知ってしまうとpの値が漏れてしまうからです。しかし、実際にはその漏洩のリスクは非常に限られています──正確には、決定的Diffie-Hellman問題は簡単ですが、計算的なバージョンは依然として「計算上不可能（computationally infeasible）」です。少なくとも、その難易度はこの値を知らないのとほぼ同じです。

「ペアリング」を理解する第三の方法は、私たちが議論しているほとんどの使用状況において最も示唆に富む方法かもしれません。もし楕円曲線上の点を一方向暗号関数（つまりencrypt(p) = p * G = P）と見なすと、従来の楕円曲線の数学的原理は変数間の線形制約を検証することを可能にします（例えばP = G * p、Q = G * q、R = G * rで、5 * P + 7 * Q = 11 * Rを検証することは実際には5 * p + 7 * q = 11 * rを検証することです）。楕円曲線ペアリングは、変数間の二次制約を検証することを可能にします（e(P, Q) * e(G, G * 5) = 1を検証することは実際にはp * q + 5 = 0を検証することです）。二次制約を実現できれば、決定的閾値署名やQAP（quadratic arithmetic programs、ゼロ知識証明の一種）などの興味深い応用が可能になります。

さて、私たちが上で導入したe(P, Q)という演算子は一体何なのでしょうか？それが一組の「ペアリング」です。数学者たちは時々それを「双線形写像」と呼びます。「双線形」とは、ここでは基本的に以下の条件を満たすことを意味します：

e(P, Q + R) = e(P, Q) * e(P, R)
e(P + S, Q) = e(P, Q) * e(S, Q)

ここでの+とは任意の演算子であることに注意してください。新しい数学的オブジェクトのクラスを新たに構築する際、抽象代数では+とがどのように「定義」されているかは重要ではなく、私たちが慣れ親しんでいる演算と一致していれば良いのです。例えばa + b = b + a、(a * b) * c = a * (b * c)、(a * c) + (b * c) = (a + b) * cのように。

もし今、P、Q、R、Sが単なる数字であれば、ペアリング関数は非常に簡単に構築できます。私たちはe(x, y) = 2^(xy)と定義できます。そうすると、次のようになります：

e(3, 4 + 5) = 2^(3 * 9) = 2²⁷
e(3, 4) * e(3, 5) = 2^(3 * 4) * 2^(3 * 5) = 2¹² * 2¹⁵ = 2²⁷

これは確かに双線形です！

しかし、このような単純なペアリングは暗号学には適していません。なぜなら、整数上で単純に動作する数学的オブジェクトを分析するのは非常に簡単だからです。整数の性質により、除算、対数など多くの操作が容易になります。整数には「公開鍵」や「一方向関数」の概念もありません。さらに言えば、上で説明したようなペアリングは可逆的です。xを知り、e(x, y)を知っていれば、除算と対数を使ってyを計算できます。私たちが求める数学的構造は、できるだけ「ブラックボックス」に近いものでなければなりません。つまり、加減乗除はできますが、それ以上はできません。この時、楕円曲線と楕円曲線ペアリングが役立ちます。

人々は、楕円曲線の点上に双線形写像を設計できることを発見しました──つまり、入力が楕円曲線上の2つの点PとQであるとき、関数e(P, Q)を構築してF_p¹²の要素にマッピングします（少なくともこの特定の状況では十分であり、この規範は曲線の詳細によって異なりますが、後で再度言及します）。しかし、これを実現するための数学は非常に複雑です。

まず、素数体（prime fields）と拡張体（extension fields）を紹介します。上の図に描かれた曲線は美しいですが、それは曲線の方程式が通常使用される実数上で定義されていると仮定した場合にそのように見えるからです。もし私たちが本当に暗号学で実数を使用するなら、対数で「逆戻り」できてしまい、すべてが無意味になります。さらに、実数を保存するために必要な空間は無限に長くなる可能性があります。したがって、私たちは実数体の数字を使用します。

素数体は、数字0, 1, 2, …, (p−1)からなる集合で構成され、ここでpは素数であり、その演算は次のように定義されます：

a + b: (a + b) % p
a * b: (a * b) % p
a - b: (a - b) % p
a / b: (a * b^(p-2)) % p

基本的に、すべての演算はpでの剰余（modulo）で行われます（ここでの剰余演算の概要）。除算は特例です。一般的に、3/2は整数ではありませんが、私たちは整数のみを扱いたいので、整数xを探してx * 2 = 3となるようにします。ここでの*は上で定義した剰余乗法を指します。幸いにも、フェルマーの小定理により、除算の指数定義は必要を満たしますが、さらに効率的に計算する方法として拡張ユークリッドアルゴリズムを使用することもできます。例えばp = 7の場合、以下のいくつかの例があります：

2 + 3 = 5 % 7 = 5
4 + 6 = 10 % 7 = 3
2 - 5 = -3 % 7 = 4
6 * 3 = 18 % 7 = 4
3 / 2 = (3 * 2^5) % 7 = 5
5 * 2 = 10 % 7 = 3

このような演算を操作しようとすると、それが前後一貫しており、すべての一般的な規則を満たすことがわかります。最後の2つの例は(a / b) * b = aを示しており、また(a + b) + c = a + (b + c)、(a + b) * c = a * c + b * c、そして他の高校で学んだ好きな代数の等式も引き続き機能します。実際に使用される楕円曲線、点、等式は通常素数体上で演算されます。

次に拡張体について話しましょう。あなたは以前に拡張体を見たことがあるかもしれません。数学の教科書で最もよく見られる例は複素数体であり──実数体にsqrt(-1) = iという新しい要素を加えることで拡張されます。簡単に言えば、拡張体とは、既存の体の上に「新しい要素」を「発明」し、その新しい要素と既存の要素との関係を定義することです（先ほどの例ではi² + 1 = 0のように）；この関係式は既存の数字では満たされないため、この新しい要素を「古い要素のすべての線形結合（linear combination）」から構成される集合に加えることが構築された集合です。

私たちは素数体を拡張することもできます。例えば、7の剰余体に先ほど述べたiを加えると、次のようになります：

(2 + 3i) + (4 + 2i) = 6 + 5i
(5 + 2i) + 3 = 1 + 2i
(6 + 2i) * 2 = 5 + 4i
4i * (2 + i) = 3 + i

最後の等式は理解しにくいかもしれません。実際、その等式の最初のステップは左側の乗法を分配して4i * 2 + 4i * iに変え、8i - 4を得ることです。私たちは7の剰余環で演算を行っているため、この数字はi + 3に変わります。除算の部分は次のようになります：

a / b : (a * b^(p²-2)) % p

ここでフェルマーの小定理の指数はpからp²に変わりますが、もちろん拡張ユークリッドアルゴリズムを使用してより効率的に計算することもできます。体の任意の要素xに対してx^(p² − 1) = 1が成り立つため、私たちは(p² − 1)を「体の乗法群の階」と呼びます。

実数体において、代数基本定理はその二次拡張（quadratic extension）：複素数体が完備であることを保証します（訳者注：これは代数的閉包を意味し、実数体も完備性を持ちますが拡張可能です）──この体はこれ以上拡張できません。なぜなら、すべての可能な新しい要素jと既存の複素数との間に満たすべき数学的関係（厳密には多項式で定義される数学的関係）が、すでに体内の要素によって満たされているからです。しかし、素数体にはこの問題はなく、三次拡張（cubic extension）を行うことができます（新しい要素wと既存の要素との関係式は三次多項式であり、したがって1, w, w²は線形独立（linear independent）です）、高次拡張、さらには拡張の再拡張なども可能です。楕円曲線はこれらの剰余演算の複素数の上に構築されています。

これらの数学をどのようにプログラムコードに実装するかに興味がある場合、ここに素数体および拡張体の実装例があります。

さて、楕円曲線ペアリングに戻りましょう。楕円曲線ペアリング（私たちが議論しているペアリングはその一種ですが、ペアリングの論理は類似しています）は、G2 × G1 → Gtの写像であり、ここで：

• G1は楕円曲線であり、その上の点はy² = x³ + bの形を満たし、点のx, y座標はF_pの要素です（つまり、彼らは普通の数字ですが、算術演算はある素数の剰余で行われます）。
• G2も楕円曲線であり、同様にG1の曲線を満たしますが、G2の要素のx, y座標はF_p¹²の要素です（これは先ほど述べた複素数であり、私たちは12次多項式w¹² − 18w⁶ + 82 = 0を満たす魔法の数字wを定義します）。
• Gtは楕円曲線の演算結果から形成される集合です。私たちが議論している曲線において、GtはF_p¹²（G2と同じ複素数を使用します）。

それが主に満たさなければならない性質は双線形であり、この文脈では次のように表されます：

e(P, Q + R) = e(P, Q) * e(P, R)
e(P + Q, R) = e(P, R) * e(Q, R)

（訳者注：ここでの双線形は正確には「整数上の双線形（bilinearity over ℤ）」であり、ここで議論されている楕円曲線上の点はすべて整数点であり、乗法と加法の定義は整数演算を行った後に剰余を取るため、自然にいくつかの線形性を満たしています）

ペアリング関数を選択する際には、2つの重要な基準があります：

• 演算が十分に効率的であること（例えば、すべての点に対して離散対数を取ってすべてを掛け合わせることができる簡単なペアリング方法ですが、これに必要な計算コストは楕円曲線暗号を破るのと同じくらい困難であるため、これは考慮されません）
• 非退化（もちろんe(P, Q) = 1と単純に定義することはできますが、それは特に有用なペアリングではありません）

では、私たちはこれをどうやって実現するのでしょうか？

ペアリング関数が機能するための背後にある数学は非常に困難であり、私たちがこれまで見てきたものを超える高度な代数が必要ですが、私は大まかに説明します。まず、「因子（divisor）」の概念を定義する必要があります。基本的に、これは楕円曲線上の点に作用する関数を表現する別の方法です。関数の因子は、関数がいくつの零点と無限大の値を持つかを計算します。いくつかの例を見てみましょう。点P = (Px, Py)を選定し、次の関数を考えます：

f(x, y) = x − P_x

その因子は[P] + [−P] − 2 * [O]です（ここでの角括弧は、ある点が関数の零点や無限大の値を持つ点の集合に現れることを示し、点そのものではありません；[P] + [Q]と[P + Q]は異なります）。理由は以下の通りです：

• この関数はP点での値が零であるため、xがPxを取るとx − Px = 0になります。
• この関数は−P点での値が零であるため、−PとPのx座標は同じです。
• この関数はxが無限大に近づくと無限大に近づくため、私たちはこの関数がO点で無限大の値を取ると言います。この無限遠点を計算するには2回計算する必要があるため、Oは−2の係数を持ちます（負号は無限遠点であるため零点とは異なり、2は2回計算されるためです）。

計算の理由は次のようになります：この曲線の方程式はx³ = y² + bであり、xが増加すると、y²が同じスケールに達するためにはyがxの1.5倍の速度で増加する必要があります。したがって、線形関数がxのみを含む場合、その無限大の項の係数は2ですが、yを含む場合はその係数は3になります。

次に、線の関数を考えます：

ax + by + c = 0

ここでa、b、cはこの線が点Pと点Qを通るように選定されます。楕円曲線の加法の動作に従い、この線も必ず−P−Q点を通ります。無限大に向かうとき、xとyの両方に依存するため、因子は[P]+ [Q] + [−P−Q] − 3 * [O]です。

私たちはすべての「有理関数」（つまり、点座標が有限回の加減乗除演算で定義される関数）が唯一の因子に対応し、せいぜい定数を掛けるだけであることを知っています（つまり、2つの関数FとGが同じ因子を持つ場合、必ず定数kが存在してF = G * kとなります）。

任意の2つの関数FとGに対して、(F * G)の因子はFとGの因子の和に等しい（数学の教科書では(F * G) = (F) + (G)と見られます）。したがって、例えばf(x, y) = P_x − xの場合、(f³) = 3 * [P] + 3 * [−P] − 6 * [O]となります；Pと−Pが3回計算されるのは、特定の数学的意味においてf³が「3倍速く」0に近づくからです。

ある定理に注意してください。もしあなたがある因子の「角括弧」を取り除くと、その点の演算結果は必ずOになります（[P] + [Q] + [−P−Q] − 3 * [O]を操作するとP + Q − P − Q − 3 * O = Oになります）、そしてこの性質を持つ因子はその関数の因子になります。

さて、私たちはテイトペアリング（Tate pairing）を見始めることができます。以下の因子で定義された関数を考えます：

• (F_P) = n * [P] − n * [O]、ここでnはG1の階数であり、すなわちすべてのPに対してn * P = Oです。
• (F_Q) = n * [Q] − n * [O]。
• (g) = [P + Q] − [P] − [Q] + [O]。

さて、この積FP * FQ * g^nを見てみましょう。その因子は：

n * [P] − n * [O] + n * [Q] − n * [O] + n * [P + Q] − n * [P] − n * [Q] + n * [O]

簡略化すると、次のようになります：

n * [P + Q] − n * [O]

この因子の形式はFPとFQの因子に一致します。したがって、FP * FQ * g^n = F_(P + Q)が成り立ちます。

次に「最終指数（final exponentiation）」と呼ばれる操作を行い、前述の演算の結果（FP、FQなど）をz = (p¹² − 1) / nの指数に自乗します。ここでp¹² − 1はFp¹²の乗法群の階です（言い換えれば、すべてのx ϵ Fp¹²に対してx^(p¹² − 1) = 1です）。注意してください。もしこの指数をすでにn次の結果に適用すると、ある要素の(p¹² − 1)次方が得られ、結果は1になります。したがって、最終指数のステップの後、g^nは消え、FP^z * FQ^z = F_(P + Q)^zが得られます。これにより、双線形性の一部が得られます。

もしあなたが2つのパラメータで双線形である関数を構築したい場合、より難解な数学が必要であり、FPを計算するだけでなく、FPの因子を計算し、さらに進めて完全なテイトペアリングを得る必要があります。より多くの結論を証明するためには、「線形同等性（linear equivalence）」やワイルの再帰性（Weil reciprocity）などの概念を理解する必要があります。これらの概念の詳細はこちらやこちらで見ることができます。

ここでは、テイトペアリングの修正版── Optimal Ate Pairingを実装しました。このコードには、ミラーアルゴリズムを使用してF_pを計算する実装も含まれています。

実際、このようなペアリングを使用することは両刃の剣のようなものです。一方では、このペアリングを利用して異なる合意を実現できることを意味しますが、他方では、どの楕円曲線を使用するかを特に注意深く選択する必要があることを意味します。

各楕円曲線には、埋め込み次数（embedding degree）と呼ばれる値があります──最小の整数kで、p^k − 1がnの倍数である（pは体で使用される素数で、nは曲線の階です）。上記の体ではk = 12ですが、従来の楕円曲線暗号学（ペアリングを考慮しない場合）で使用される体の埋め込み次数は通常非常に大きく、計算上ペアリングを計算することが不可能になるほどです。しかし、私たちが注意を怠ると、k = 4やk = 1の体を構築してしまう可能性があります。

k = 1の場合、楕円曲線上の「離散対数問題」（P = G * pという点だけが知られている場合にpの値を計算すること；つまり、楕円曲線の秘密鍵を「解読」する際に必要な問題）は、F_p上の比較的簡単な問題に退化する可能性があります（この方法はMOV攻撃と呼ばれます）。埋め込み次数が12以上の楕円曲線を使用することで、この退化が不可能であることが保証されます。または、退化した問題が「通常の」方法で公開鍵から秘密鍵を計算するのと同じくらい困難になるほど複雑になります。現在、すべての標準的な曲線パラメータは慎重に検査されており、この問題の影響を受けません。