POKEx: Performance analysis of POKE-key exchange and SIDH-variants

インターネットを、誰もが秘密の手紙を送り合っている巨大で賑やかな都市だと想像してみてください。これらの手紙を泥棒から守るために、私たちは「暗号化」と呼ばれる「鍵（ロック）」を使います。何十年もの間、最高の鍵は、一方の方向では簡単に行えるが、逆方向に解くのは非常に難しい数学の問題（例えば、絵の具を混ぜ合わせるようなもの）を使用して作られてきました。しかし、科学者たちは、将来、超強力なコンピュータ（量子コンピュータと呼ばれます）が登場したとき、これらの鍵を瞬時に解いてしまい、私たちの秘密を丸裸にしてしまうのではないかと懸念しています。これを防ぐために、研究者たちは「イソジェニー」と呼ばれる、奇妙で美しい数学の一分野に基づいた新しい鍵を構築しています。イソジェニーを、異なる形（数学的な曲線）同士をつなぐ特別な「橋」だと考えてみてください。この鍵の秘密は、その橋を渡る際に通る特定の「経路」にあります。長い間、最も人気のある橋のデザインは「SIDH」と呼ばれていました。SIDHは、鍵が非常に小さく高速であったため、私たちの未来のデジタル世界を守るための有力な候補となっていました。

しかし、2023年、ある研究者ペアが、このSIDHという橋を壊す巧妙なトリックを発見しました。彼らは、橋の設計者が、誰が見ても経路の地図が見えてしまうようなミスを犯しており、それによって数秒で秘密のルートを特定できてしまうことを突き止めたのです。これは大きな打撃でした。最も有望な「量子耐性」を持つ鍵が、実は破られていたことを意味したからです。これ以来、科学者たちは、地図をもっとうまく隠せる新しい橋を必死に作ろうとしてきました。ある者は地図を毛布で覆い（マスキング）、またある者は異なる素材で橋を作ろうとしました。大きな疑問は、「壊れにくく、かつ現実世界で使用できるほど高速な橋を構築できるのか？」という点でした。

「POKEx」と題されたこの論文は、この混沌とした建設現場に足を踏み入れ、「POKÉ」と呼ばれる新しく輝かしい橋のデザインをテストしています。著者であるHyeonhak Kim氏とSuhri Kim氏は、POKÉという暗号方式を、完全な鍵交換システム（彼らはこれをPOKExと呼んでいます）へと発展させ、壊れたSIDHの橋を修復しようとしている他のトップレベルの候補たちと競わせることにしました。彼らは単に推測したのではなく、これらのシステムの動作バージョンを実際に構築し、強力なコンピュータで時間を計測しました。彼らの主な発見は、POKExが現在、イソジェニーベースの橋の中で最も高速で効率的であるということです。テストにおいて、POKExは次に優れた代替案（terSIDH）よりも約21倍速く、もう一つの人気のあるデザイン（CSIDH）よりも約65倍速かったのです。これは、他の種類の量子安全な鍵よりは依然として遅いものの、その速度と極めて小さなサイズにより、非常に有望な候補であることを示しており、インターネットを低速化させることなく、私たちのデジタルの秘密を守る方法を提供しています。

壊れた橋と新しい解決策の物語

この論文がなぜ重要なのかを理解するためには、まず「橋」の問題を見る必要があります。暗号の世界において、「鍵交換」とは、二人の人間が言葉に出すことなく、秘密のパスワードに合意することのようなものです。長い間、SIDHシステムはスタープレイヤーでした。それは「超特異楕円曲線」を使用しており、これは数学的な宇宙における複雑でうねった形のようなものです。SIDHの魔法は、これらの曲線上の特定のランドマーク（目印）である「ねじれ点（torsion points）」を使用して、橋を築いたことにありました。このシステムは非常に効率的であったため、鍵（デジタル的な軽量の小さなロック）が小さく、非常に高速でした。

しかし、SIDHの橋には致命的な欠陥がありました。橋を築くために、システムは使用したランドマーク（ねじれ点）に関する情報を公開しなければなりませんでした。2023年、CastryckとDecruは、これらの公開されたランドマークと、「Kaniのglue-and-split」と呼ばれる巧妙な数学的トリックを組み合わせることで、秘密の経路を再構築する方法を見つけ出しました。それはまるで、宝物へと直結するパン屑の跡を残してしまったようなものでした。この攻撃が発見されると、SIDHは壊れたとみなされ、未来のインターネットセキュリティの候補リストから外されました。

橋を直すためのレース

SIDHが崩壊した後、暗号コミュニティは諦めませんでした。彼らはSIDHに代わる新しい橋を築き始めました。ある者は、ランダムなノイズでランドマークを覆うことで隠そうとしました（M-SIDHと呼ばれる手法）。またある者は、「人工的な方位（artificial orientation）」を用いることで、橋の形自体を変えようとしました（terSIDH）。また、同じ攻撃の影響を受けない別のタイプの橋であるCSIDHもありましたが、それには独自の速度の問題がありました。

問題は、これらの新しい橋が、遅すぎるか、あるいは大きすぎることでした。ランドマークをノイズで覆うには、安全性を保つために非常に大きな数が必要であり、それがロックを重く、使用を遅くさせてしまいました。橋の形を変えること（terSIDH）は効果がありましたが、依然として危険を伴う可能性のある速度のばらつきがありました。コミュニティは、安全かつ高速なソリューションを必要としていたのです。

POKEx：スピードの怪物

ここで、この論文の新しいヒーローであるPOKExが登場します。POKExは、最近BassoとMainoによって提案されたPOKÉというスキームに基づいています。この論文の著者たちは、POKÉを、鍵を生成し秘密を安全に交換するために必要なすべてのステップを備えた完全な鍵交換システムへと作り変えました。

POKExの秘訣は、その「ランドマーク」の扱い方にあります。古いSIDHのように一次元的な経路を使用するのではなく、POKExは「二次元的な表現」を使用します。川を渡る場面を想像してみてください。SIDHは一本の板の上を歩くようなものでした。もし誰かがあなたの足跡を見れば、あなたの経路を特定できてしまいます。しかし、POKExは、二方向に同時に動くことができるグリッド状の板の上を歩くようなものです。これにより、経路を推測することが非常に困難になります。さらに、POKExは特殊な数学体（$2^a3^b5^c-1$ の形の素数）を使用しており、これにより、より大きく遅い数字を使用しなければならない他の新しい橋とは異なり、非常に高速な計算が可能になります。

大対決：数字が示すもの

著者たちは単にPOKExについて語っただけではありません。彼らはそれをテストにかけました。彼らは、POKExをM-SIDH、terSIDH、CSIDHといった他のトップレベルの候補と並行して実行するためのソフトウェアを構築しました。そして、すべてを同じセキュリティレベル（政府の最高機密を保護するための標準であるNISTセキュリティレベル1）に設定し、鍵交換にかかる時間を計測しました。

結果は驚くべきものでした。

• M-SIDHは、POKExがわずかな時間で行うことを行うのに、190秒近くかかり、最も遅いグループでした。著者らは、これが実用的な使用には不向きであることを指摘しています。
• terSIDHはM-SIDHよりはるかに速かったものの、依然として約6.5秒かかりました。
• CSIDHは約20秒かかりました。
• しかし、POKExは、わずか 306.95ミリ秒（約0.3秒）で任務を完了しました。

これを比較すると、POKExはterSIDHよりも 21.21倍速く、CSIDHよりも 64.97倍速い ことになります。これにより、POKExは現在、イソジェニーベースの鍵交換におけるチャンピオンとなりました。

それは完璧なのか？

この論文は、これを「完璧な」解決策とは呼ばないよう注意深く記述されています。POKExはイソジェニーの橋の中では最速ですが、ML-KEM（テストではわずか0.10ミリ秒でした）のような他の種類の量子安全な鍵と比較すると、依然として低速です。しかし、著者らは重要なトレードオフを指摘しています。ML-KEMは高速ですが、その「鍵（公開鍵と暗号文）」は巨大であり、インターネット上で多くのスペースを占有します。一方で、POKExは非常に小さな鍵（公開鍵はわずか324バイト）を持っており、これは帯域幅の使用量が少ないことを意味します。インターネットの速度やデータ制限が重要となる世界において、この小さなサイズは大きな利点となります。

結論

この論文は、古いSIDHという橋は壊れたものの、新しい安全な橋への道は開かれていることを示しています。POKExは現在、イソジェニー・ファミリーの中で最も有望な候補であり、高い速度と小さなサイズという稀な組み合わせを提供しています。これは、私たちがデジタルの生活を遅らせることなく、量子耐性を持つ鍵を構築できることを証明しています。他の量子安全な手法の速度に追いつくためにはまだ課題がありますが、その効率性は、時間の節約と同じくらいデータの容量節約が重要となる状況において、未来のインターネットを安全に保つための不可欠なツールになり得ることを示唆しています。