Cycles of supersingular elliptic curves for pairing-based proof systems

デジタル世界において、秘密そのものを明かすことなく、自分がその秘密を知っていることを証明することは、強力なツールとなります。これは現代の暗号技術の核心であり、「証明システム」は、計算全体を再実行する必要なく、コンピュータがユーザーに対して計算が正しく行われたことを納得させることを可能にします。これらの証明が実世界で有用であるためには、短く、かつ検証が高速である必要があります。「簡潔な非対話型引数（succinct non-interactive argument）」として知られる特定の種類の証明は、この技術の礎石となっています。これらの証明をさらに強力なものにするため、研究者たちはそれらを積み重ねる方法を開発しました。これにより、一つの証明が別の証明を検証することが可能になり、無限に成長できる信頼の連鎖が生まれます。「再帰（recursion）」と呼ばれるこのプロセスは、今日使用されている最も高度なプライバシーおよびスケーリング技術の背後にあるエンジンです。しかし、これらの連鎖を構築するには、非常に特殊な数学的基盤、すなわち、パズルのピースのように完璧に組み合わさる楕円曲体のペアが必要です。長年、この記述に適合する既知のピースは、希少で発見が困難であり、数も限られていたため、この技術のボトルネックとなっていました。

研究チームは、これら不可欠な曲線ペアを生成する新しい方法を発見し、これまでアクセス不可能であった広大な供給源を解き放ちました。彼らは、「超特異曲線（supersingular curves）」と呼ばれる異なる種類の数学的対象を使用することで、これらのパズルのピースのようなペアの無限のファミリーを構築できることを見出しました。以前の手法は、新しいペアを見つけることが運と膨大な計算努力を要する限定的な条件に依存していましたが、この新しいアプローチは、ほぼあらゆる選択された数値に対して信頼性を持って機能します。研究者たちは、これらの新しいサイクルを構築し、それらを他の効率的な曲線と接続して「ロリポップ（lollipops）」と呼ぶ構造を形成できることを実証しました。これらの構造により、証明の最初の重い処理を小さな高速な体（field）上で行い、再帰的な積み重ねをより大きな安全なサイクル上で行うことができます。実用的な探索において、彼らはこれらの新しい構造の18個の異なる例を構築することに成功し、次世代の安全なデジタルシステムのための柔軟で豊富なリソースを提供しました。

この発見への道のりは、既存の技術における限界から始まりました。現在のこれらの再帰的証明システムの標準は、しばしば「サイクル」と呼ばれる、二つの楕円曲体の特定の配置に依存しています。この配置では、第一の曲線の点数が第二の体を定義するサイズの大きさと一致し、その逆も同様です。この繊細なバランスにより、証明が一方の曲線から他方へとシームレスに受け渡されることが可能になります。10年以上にわたり、このようなサイクルを構築する唯一の既知の方法は、「通常の（ordinary）」曲線を使用するものであり、これは宮地、中林、および高野によって開発された手法でした。この手法は理論的には機能しますが、実際には極めて疎（sparse）です。新しいペアを見つけるには、数字が絶妙に合致しなければならない複雑な方程式を解く必要があります。セキュリティ要件が高まるにつれ、有効なペアに偶然遭遇する可能性はゼロに近づきます。それは、精密な基準を満たす特定の砂粒を探すようなものです。ビーチは無限にありますが、正しい砂粒は極めて稀です。この希少性により、開発者は、より古い、安全性の低いパラメータを使用するか、あるいは短期的で限定的な連鎖のために、無限の再帰という理想を断念せざるを得なくなりました。

研究者たちは、ボトルネックはサイクルという概念自体ではなく、使用されている曲線の種類にあることに気づきました。彼らは「超特異（supersingular）」曲線に注目しました。これらは、標準的な暗号学ではそれほど一般的ではありませんが、この特定のタスクに理想的な独自の特性を持つ、異なる種類の数学的バリエーションです。トレードオフとして、これらの曲線はわずかに大きな数学的体上で定義される必要があり、一部の計算が少し重くなります。しかし、そのメリットは圧倒的です。新しい構成法は、基本的な素数判定を満たしていれば、選択されたほぼすべての数値に対して機能します。希少な幸運な数字を探し出す必要はありません。研究者たちは、有効な数値に対して、有効な一対の超特異曲線を即座に生成できることを示しました。これにより、問題は「宝探し」から「製造プロセス」へと変貌しました。散在するわずかな例を見つけるのではなく、オンデマンドで無限のサイクルを生産できるようになったのです。

このコンセプトが実世界で機能することを証明するために、チームは単に理論に頼るだけでなく、具体的な例を見つけるための検索エンジンを構築しました。彼らは「ロリポップ」と呼ばれる構造の構築に取り組みました。キャンディケインを想像してください。棒の部分は効率的な曲線の連鎖であり、上の丸い部分は再帰的なサイクルです。棒の部分により、証明を小さな高速な体で開始でき、初期の計算ステップが非常に迅速になります。丸い部分であるサイクルにより、証明を制限なく再帰的に積み重ね、検証することができます。研究者たちは、ペル方程式（Pell equation）として知られる特定の種類の手がかりとなる数パズルを解くことで、これらの構造を見つけるアルゴリズムを開発しました。彼らは強力なコンピュータを用いてこのアルゴリズムを実行し、数百万の可能性を探索しました。探索は成功しました。彼らは、80ビットから128ビット以上までのセキュリティレベルをサポートする、さまざまなサイズの18個の異なるロリポップの例を見つけ出しました。彼らの例の一つである956ビットの体を持つ大きなインスタンスは、実用的な関心の境界さえも押し広げ、これらの構造が将来のセキュリティニーズを満たすためにスケールできることを示しました。

これらの発見の重要性は、システム設計者に提供する柔軟性にあります。従来の手法では、他に選択肢がないため、設計者は特定の、しばしば非効率的なパラメータを使用することを強制されていました。より高いセキュリティを求める場合、パフォーマンスの低下を受け入れるか、あるいは再帰の制限を短くしなければなりませんでした。新しい超特異サイクルを用いることで、設計者は、数学が特に高速に計算できる体や、ハードウェアアクセラレーションに役立つ特定の特性を持つ体など、速度に最適化されたパラメータを選択できます。また、ペアリングに適しているわけではないものの、証明の初期ステップにおいて極めて効率的な他の種類の曲線に、これらのサイクルを接続することもできます。このように、コンポーネントを組み合わせ、特定のアプリケーション向けにカスタムの「ロリポップ」を作成できる能力は、以前の技術では不可能でした。研究者たちは、新しい曲線の一部がやや大きくなるものの、システムの他の部分を最適化できる能力と、利用可能なサイクルの圧倒的な豊富さを考えれば、そのトレードオフは価値があるものだと指摘しています。

論文は、これが建設的な突破口であることを強調して締めくくられています。研究者たちは、これらのサイクルが存在することを証明しただけでなく、それらを構築するためのツールと、18個の動作する例のカタログを提供しました。彼らは、理論的な利点が大きな体による実用的なコストとどのように釣り合うかを測定するために、次のステップはこれらの新しいサイクルを実際のソフトウェアに実装することであると認めています。しかし、扉は開かれました。再帰的証明システムの成長を制限していた希少性は取り除かれました。通常の曲線から超特異な曲線へとシフトすることで、研究者たちは、より安全で、かつ現実世界の多様なニーズに適応可能な証明システムを実現するために必要な、数学的構成要素の新しい無限の供給源を提供したのです。