ヴィタリック・ブテリン経由 ヴィタリック・ブテリンのブログ
これは次の投稿のミラーです https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
トリガー警告: 数学。
決定論的しきい値署名、zk-SNARK、その他のより単純な形式のゼロ知識証明を含む、さまざまな構造の背後にある重要な暗号化プリミティブの 30 つは、楕円曲線ペアリングです。楕円曲線ペアリング (または「双線形マップ」) は、暗号化やデジタル署名などの暗号アプリケーションに楕円曲線を使用してきた XNUMX 年にわたる歴史に最近追加されたものです。ペアリングは「暗号化された乗算」の形式を導入し、楕円曲線ベースのプロトコルでできることを大幅に拡張します。この記事の目的は、楕円曲線のペアを詳しく説明し、その仕組みの概要を説明することです。
初めて読むとき、あるいは 10 回目でさえ、ここにあるすべてを理解することは期待されていません。これは本当に難しいです。しかし、この記事が内部で何が起こっているのかについて少しでも理解していただければ幸いです。
楕円曲線自体は理解するのが非常に簡単ではないトピックであり、この記事では通常、楕円曲線がどのように機能するかを理解していることを前提としています。そうでない場合は、入門書としてこの記事をお勧めします。 https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/。簡単にまとめると、楕円曲線暗号には「ポイント」と呼ばれる数学的オブジェクト (これらは (�,�) 座標を持つ文字通りの 2 次元の点です) と、それらを加算および減算するための特別な式 (すなわち、�= の座標を計算するための) が含まれます。 �+�)、点に整数を乗算することもできます(つまり、�⋅�=�+�+…+�。ただし、� が大きい場合は、より高速に計算する方法があります)。
ポイントの追加をグラフで見ると次のようになります。
「無限遠点」 (�) と呼ばれる特別な点が存在します。これは、点演算におけるゼロに相当します。常に �+�=� になります。また、曲線には「」があります。注文「;任意の � に対して�⋅�=� となるような数値 � が存在します (もちろん、�⋅(�+1)=�、�⋅(7⋅�+5)=�⋅5 なども同様です)。また、一般的に合意されている「生成点」� もあり、これはある意味で数字の 1 を表すと理解されています。理論的には、曲線上の任意の点 (� を除く) は� になる可能性があります。重要なのは、� が標準化されていることだけです。
ペアリングは、楕円曲線の点に関する特定の種類のより複雑な方程式をチェックできるようにするという点でさらに一歩進んでいます。たとえば、�=�⋅�、�=�⋅�、および �=�⋅� の場合、 �⋅�=� ではなく、入力として �、�、� のみを使用します。 P を知っているだけで � に関する情報が漏洩しているため、楕円曲線の基本的なセキュリティ保証が破られているように見えるかもしれませんが、漏洩は高度に抑制されていることが判明しています。 決定的なディフィー・ヘルマン問題 は簡単ですが、計算上のディフィー ヘルマン問題 (上記の例では � と � がわかっているため、 コンピューティング �=�⋅�⋅�) と 離散対数問題 (� から� を回復すること) は依然として計算上実行不可能です (少なくとも、以前であれば)。
ペアリングが何を行うのかを見るための 3 番目の方法は、ここで説明するほとんどのユースケースにとっておそらく最もわかりやすい方法です。それは、楕円曲線の点を一方向の暗号化された数値 (つまり、����) として見る場合です。 ��(�)=�⋅�=�)、従来の楕円曲線の計算では次のことを確認できます。 線形 数値の制約 (たとえば、�=�⋅�、�=�⋅�、および�=�⋅�の場合、5⋅�+7⋅�=11⋅�をチェックすることは 本当に 5⋅�+7⋅�=11⋅�)を確認すると、ペアリングで確認できます 二次 制約 (例: �(�,�)⋅�(�,�⋅5)=1 のチェックは 本当に �⋅�+5=0 であることを確認します)。そして、二次関数まで進むと、決定論的なしきい値シグネチャ、二次演算プログラム、その他すべての優れた機能を使用できるようになります。
さて、上で紹介したこの面白い �(�,�) 演算子は何でしょうか?これがペアリングです。数学者はそれを「」と呼ぶこともあります。 双線形マップ;ここでの「双線形」という言葉は基本的に、次の制約を満たすことを意味します。
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
+ と ⋅ は任意の演算子になることに注意してください。新しい種類の派手な数学オブジェクトを作成するとき、抽象代数では + と ⋅ がどのようなものであるかは気にされません。 定義済みの、通常の方法で一貫している限り、たとえば。 �+�=�+�、(�⋅�)⋅�=�⋅(�⋅�)、および (�⋅�)+(�⋅�)=(�+�)⋅�。
�、�、�、�が単純だったら 番号であれば、単純なペアリングを作成するのは簡単です。�(�,�)=2�� を実行できます。すると、次のことがわかります。
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
バイリニアですよ!
ただし、このような単純なペアリングは暗号化には適していません。これは、ペアリングが処理するオブジェクトが単純な整数であり、分析が簡単すぎるためです。整数を使用すると、除算、対数の計算、その他のさまざまな計算が簡単になります。単純な整数には、「公開鍵」や「一方向関数」の概念がありません。さらに、上記のペアリングを使用すると、過去に遡って、� を知り、�(�,�) を知ることができ、単純に割り算と対数を計算して� を求めることができます。私たちは、足し算、引き算、掛け算、割り算ができる「ブラック ボックス」にできるだけ近い数学的オブジェクトを望んでいます。 でも他には何もしない。ここで、楕円曲線と楕円曲線のペアが登場します。
楕円曲線点上の双一次マップを作成できることがわかりました。つまり、入力 � と � が楕円曲線点であり、出力がいわゆる(��)12 要素 (少なくともここで取り上げる特定のケースでは、詳細は曲線の詳細によって異なります。これについては後ほど説明します) ですが、その背後にある計算は非常に複雑です。
まず、素体と拡張体について説明します。この投稿の前半の図にあるきれいな楕円曲線は、曲線の方程式が通常の実数を使用して定義されていると仮定した場合にのみ、そのように見えます。しかし、実際に暗号化で通常の実数を使用すると、対数を使用して「逆戻り」することができ、すべてが壊れてしまいます。さらに、数値を実際に保存して表現するために必要なスペースの量は、任意に増加する可能性があります。したがって、代わりに数値を使用します。 素体.
素数フィールドは 0,1,2…�−1 の数値セットで構成されます。� は素数であり、さまざまな演算は次のように定義されます。
�+�:(�+�) % �
�⋅�:(�⋅�) % ��
�−�:(�−�) % ��
�/�:(�⋅��−2) % ��
基本的に、すべての計算は � を法として実行されます (「 こちら モジュラー数学の入門用)。除算は特殊なケースです。通常、32 は整数ではありません。ここでは整数のみを扱いたいので、代わりに ⋅2=3 のような数値を見つけようとします。ここで ⋅ はもちろん、上で定義した剰余乗算を指します。おかげで フェルマーの小定理、上に示した累乗トリックはその仕事をしますが、それを使用するより速い方法もあります。 拡張ユークリッド アルゴリズム。 �=7 と仮定します。以下にいくつかの例を示します。
2+3=5 % 7=5
4+6=10 % 7=3
2−5=−3 % 7=4
6⋅3=18 % 7=4
3/2=(3⋅25) % 7=5
5⋅2=10 % 7=3
この種の数学を試してみると、それが完全に一貫性があり、通常のルールをすべて満たしていることがわかります。上記の最後の 2 つの例は、(�/�)⋅�=�;また、(�+�)+�=�+(�+�)、(�+�)⋅�=�⋅�+�⋅�、およびあなたが知っていて大好きな他のすべての高校の代数恒等式が継続していることもわかります。同様に当てはまります。実際の楕円曲線では、点と方程式は通常、素体で計算されます。
さて、話しましょう 拡張フィールド。おそらく、拡張フィールドをすでに見たことがあるでしょう。数学の教科書で目にする最も一般的な例は、実数のフィールドが追加要素 −1=� で「拡張」されている複素数のフィールドです。基本的に、拡張フィールドは既存のフィールドを取得し、新しい要素を「発明」し、その要素と既存の要素の間の関係 (この場合、�2+1=0) を定義して、この方程式が当てはまらないことを確認することによって機能します。元のフィールドにある任意の数値について、元のフィールドの要素と作成したばかりの新しい要素のすべての線形結合のセットを確認します。
素数フィールドの拡張も行うことができます。たとえば、上で説明した素体 mod7 を � で拡張すると、次のようになります。
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
最後の結果を理解するのは少し難しいかもしれません。そこで何が起こったかというと、まず積を 4�⋅2+4�⋅� に分解すると 8�−4 が得られ、次に mod7 の計算を行っているため、�+3 になります。分割するには、次のようにします。
�/�:(�⋅�(�2−2)) % ��
フェルマーの小定理の指数が � ではなく �2 になっていることに注意してください。ただし、より効率的にしたい場合は、代わりに拡張ユークリッド アルゴリズムを拡張してその仕事を行うこともできます。この体内の任意の � に対して��2−1=1であることに注意してください。したがって、�2−1 を「体の乗法群の次数」と呼びます。
実数の場合、 代数の基本定理 複素数と呼ばれる 1 次拡張が「完全」であることを保証します。これ以上拡張することはできません。なぜなら、何らかの新しい要素間の数学的関係 (少なくとも、代数式で定義される数学的関係) については考えられないからです。 � と既存の複素数を使用すると、すでにその関係を満たす複素数を少なくとも 2 つ思いつくことができます。しかし、素体ではこの問題は発生しないため、さらに進んで XNUMX 次拡張を行うことができます (新しい要素 � と既存の体の要素との間の数学的関係は XNUMX 次方程式であるため、XNUMX、�、�XNUMX は次のようになります)すべて互いに線形独立)、高次の拡張、拡張の拡張など。そして、楕円曲線のペアが構築されるのは、この種の過給モジュラー複素数です。
これらすべての操作をコードで記述する際の正確な計算に興味がある人のために、ここではプライム フィールドとフィールド拡張が実装されています。 https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
さて、楕円曲線ペアリングに移ります。楕円曲線ペアリング (というよりも、ここで検討するペアリングの特定の形式。ロジックはかなり似ていますが、他のタイプのペアリングもあります) は、マップ �2×�1→�� です。ここで、次のとおりです。
- �1 は楕円曲線であり、点は�2=�3+� の形式の方程式を満たし、両方の座標が��の要素です(つまり、算術演算がすべて素数を法として行われることを除いて、これらは単純な数です)。
- �2 は楕円曲線であり、座標が (��)1 の要素である点を除き、点は�12 と同じ方程式を満たします (つまり、これらは上で説明した過給複素数です。新しい「魔法の数」を定義します)。 ” �、これは�12−12⋅�18+6=82 のような 0 次多項式で定義されます)
- �� は、楕円曲線の結果が入るオブジェクトのタイプです。注目する曲線では、�� は (��)12 (��2 で使用されるものと同じスーパーチャージされた複素数) です。
満たさなければならない主な特性は双線形性です。この文脈では、これは次のことを意味します。
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
他に 2 つの重要な基準があります。
- 効率的な計算能力 (たとえば、すべての点の離散対数を取得し、それらを乗算するだけで簡単にペアリングを作成できますが、これはそもそも楕円曲線暗号を解読するのと同じくらい計算的に難しいため、カウントされません)
- 非縮退 (もちろん、�(�,�)=1 と定義することもできますが、これは特に有用な組み合わせではありません)
それでは、どうやってこれをやるの?
ペアリング関数が機能する理由の背後にある数学は非常に難しく、これまでに見てきたものをさらに超えるかなりの高度な代数が必要ですが、概要を説明します。まず最初に、概念を定義する必要があります。 除数、基本的には楕円曲線点上の関数を表す別の方法です。関数の約数は基本的に関数のゼロと無限大を数えます。これが何を意味するのかを理解するために、いくつかの例を見てみましょう。ある点 ��=(��,��) を固定して、次の関数を考えてみましょう。
�(�,�)=�−��
除数は [�]+[−�]−2⋅[�] です (角括弧は、次のことを参照しているという事実を表すために使用されます) 関数のゼロと無限大のセットにおける点 � の存在、点 P 自体ではありません。 [�]+[�]は [�+�] と同じ)。その理由は次のとおりです。
- � であるため、この関数は � でゼロに等しくなります。 is �� なので、��−��=0
- −� と � は同じ� 座標を共有するため、この関数は −� でゼロに等しくなります。
- � が無限大になると関数も無限大になるため、関数は � で無限大に等しいと言います。この無限大を 2 回カウントする必要がある技術的な理由があるため、� には −XNUMX の「多重度」が加算されます (これは無限大でゼロではないため負であり、この二重カウントにより XNUMX になります)。
技術的な理由はおおよそ次のとおりです。曲線の方程式は �3=�2+� であるため、�1.5 が�2 に追いつくためには�よりも「3 倍速く」無限大に進みます。したがって、一次関数に � のみが含まれる場合は多重度 2 の無限として表現されますが、� が含まれる場合は多重度 3 の無限として表現されます。
ここで、「線関数」について考えてみましょう。
��+��+��=0
ここで、�、�、および�は、線が点�と�を通過するように慎重に選択されています。楕円曲線加算の仕組み (上部の図を参照) により、これは −�−� を通過することも意味します。そして、� と � の両方に依存して無限大になるので、約数は [�]+[�]+[−�−�]−3⋅[�] になります。
私たちは、すべての「有理関数」(つまり、点の座標に対する有限数の +、-、⋅ および / 演算のみを使用して定義された関数)が、定数による乗算までの何らかの除数に一意に対応することを知っています。 2 つの関数 � と � が同じ約数を持つ場合、定数 �) については �=�⋅� になります。
任意の 3 つの関数 � と � について、 �⋅� の約数は � の約数に� を加えたものに等しくなります (数学の教科書では (�⋅�)=(�)+(�) となります)。たとえば、�(�,�)=��−�の場合、(�3)=3⋅[�]+6⋅[−�]−3⋅[�]; � と −� は、ある数学的な意味で�0 がこれらの点で「XNUMX 倍の速さで」XNUMX に近づくという事実を考慮して「XNUMX 倍にカウント」されます。
関数の約数から「角括弧を削除」すると、点の合計は �([�]+[�]+[−�−�]−3⋅[ になるという定理があることに注意してください。 �] は、�+�−�−�−3⋅�=� のように明らかに適合し、この性質を持つ約数は関数の約数です。
これで、Tate のペアリングを確認する準備ができました。約数によって定義された次の関数を考えてみましょう。
- (��)=�⋅[�]−�⋅[�]、ここで�は�1 のオーダーです。任意の�に対して�⋅�=�
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
それでは商品��⋅��⋅��を見てみましょう。除数は次のとおりです。
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�⋅[�]
これは次のように単純化されます。
�⋅[�+�]−�⋅[�]
この除数は、上記の �� および �� の除数とまったく同じ形式であることに注意してください。したがって、��⋅��⋅��=��+�となります。
ここで、「最終べき乗」ステップと呼ばれる手順を導入します。この手順では、上記の関数の結果 (��、�� など) を ��=(��12−1)/�� 乗します。ここで、��12−1 は (��)12 の乗法群の次数です (つまり、 どれか �∈(��)12,�(�12−1)=1)。このべき乗を次の結果に適用すると、 既に �� 乗すると、��12−1 乗となり、結果は 1 になります。したがって、最後のべき乗の後、�� は相殺され、���⋅���=( �+�)�。あなたにはいくつかの双線形性があります。
さて、両方の引数で双一次関数を作成したい場合は、値の��を直接取得する代わりに、値の��を取得するという、より奇妙な数学に入る必要があります。 除数、そしてそこから完全な「テートのペアリング」が生まれます。さらに結果を証明するには、「線形等価性」や「ヴェイユの相反性」などの概念に対処する必要があり、そこからウサギの穴が続きます。これらすべてに関するその他の読み物を見つけることができます こちら および こちら.
最適な Ate ペアリングと呼ばれる、Tate ペアリングの修正バージョンの実装の場合、 ここを参照してください。コードは実装します ミラーのアルゴリズム、実際に��を計算するために必要です。
このようなペアリングが可能であるという事実は、いくぶん祝福が混在していることに注意してください。これは、ペアリングで実行できるすべてのプロトコルが可能になることを意味する一方で、楕円曲線の種類についてより注意を払う必要があることを意味します。を使用しております。
すべての楕円曲線には、 埋め込み度;基本的に、��−1 が � の倍数となるような最小の� (� はフィールドに使用される素数、� は曲線次数です)。上記のフィールド、�=12、および従来の ECC に使用されるフィールド (つまり、ペアリングを気にしないフィールド) では、埋め込み次数が非常に大きく、ペアリングの計算が計算上不可能になることがよくあります。ただし、注意しないと、�=4 または 1 のフィールドが生成されてしまう可能性があります。
�=1 の場合、楕円曲線の「離散対数」問題 (本質的には、点 �=�⋅� だけを知っていて、楕円曲線の秘密鍵を「解読」するために解決しなければならない問題を回復する) を軽減できます。 �� に関する同様の数学問題に置き換えると、問題ははるかに簡単になります (これは MOV攻撃);埋め込み次数が 12 以上の曲線を使用すると、この削減が不可能になるか、ペアリング結果に関する離散ログ問題を解決することが、少なくとも「通常の方法」で公開鍵から秘密鍵を回復するのと同じくらい難しいことが保証されます。計算上不可能です)。心配しないでください;この問題については、すべての標準曲線パラメータが徹底的にチェックされています。
zk-SNARK がどのように機能するかについての数学的説明は近々公開される予定ですので、ご期待ください。
レビューと修正を行ってくれた Christian Reitwiessner、Ariel Gabizon (Zcash より)、および Alfred Menezes に特別に感謝します。
- SEO を活用したコンテンツと PR 配信。 今日増幅されます。
- PlatoData.Network 垂直生成 Ai。 自分自身に力を与えましょう。 こちらからアクセスしてください。
- プラトアイストリーム。 Web3 インテリジェンス。 知識増幅。 こちらからアクセスしてください。
- プラトンESG。 カーボン、 クリーンテック、 エネルギー、 環境、 太陽、 廃棄物管理。 こちらからアクセスしてください。
- プラトンヘルス。 バイオテクノロジーと臨床試験のインテリジェンス。 こちらからアクセスしてください。
- ブロックオフセット。 環境オフセット所有権の近代化。 こちらからアクセスしてください。
- 情報源: プラトンデータインテリジェンス。