SIDHとSIKE：設計と暗号解読

2011年にJaoとDe Feoが提案したSupersingular Isogeny Diffie-Hellman（SIDH）は、Diffie-Hellmanに類似した公開鍵交換プロトコルですが、超特異楕円曲線上の同種写像を使用します。双方は、Fp2上の同じ超特異曲線Eから開始します。Aliceは秘密の同種写像phi_A: E -> E_A（2^a-トーション内のランダムな核）を計算し、E_Aと、phi_AによるBobのトーション生成元の像を公開します。Bobはphi_B: E -> E_B（3^b-トーション内のランダムな核）を計算し、E_Bと、phi_BによるAliceのトーション生成元の像を公開します。AliceはBobが公開したデータを使ってphi_A': E_B -> E_ABを計算し、Bobはphi_B': E_A -> E_ABを計算します。両者は共有秘密としてj(E_AB)を得ます。

SIDHで使用する特殊な素数形式p = 2^a * 3^b * f - 1（fは素数性を確保する小さな余因子）により、Fp2上の曲線Eは必要なトーション構造を持ちます。SIKEp434（NIST Level 1、128ビットのポスト量子安全性）では、p = 2^216 * 3^137 - 1、a = 216、b = 137です。これは、Aliceが2-同種写像を216段階たどり、Bobが3-同種写像を137段階たどることを意味します。鍵サイズについては、Aliceの公開鍵はE_Aと2つのFp2点（phi_A(P_B), phi_A(Q_B)）で構成され、3 * 2 * 54 = 324バイトです。SIKEp751は古典安全性192ビット／量子安全性128ビットを目標とし、公開鍵は564バイトです。これらはNIST PQC候補の中で最小の公開鍵ですが、その代償として処理速度は100～1000倍遅くなります。

SIKE（Supersingular Isogeny Key Encapsulation）は、Fujisaki-Okamoto変換を使ってSIDHから構築された、IND-CCA2安全なKEMです。SIKE.Encapsでは、ランダムなメッセージmを選び、（c0 = mをシードとするSIDH公開鍵、c1 = H2(m) XOR pk）を計算して送信します。SIKE.Decapsでは、秘密鍵を使ってc0からmを復元し、c1を検証し、整合性を確認するために（c0, c1）を再計算し、K = H3(m, c0)を出力します。FO変換により、SIDHのCPA安全な交換はCCA2安全なKEMに変換されます。SIKEはNIST PQCの全4ラウンド（2017～2022年）で競争し、広範な暗号解析を乗り越えてきましたが、2022年7月に致命的な古典攻撃が登場しました。

2011年から2022年まで、SIDHは大きな暗号解読の試みに耐えてきました。SIDHに対する既知の最良の攻撃は次のとおりです。(1) 一般的なSSIPアルゴリズム：古典計算ではO(p^{1/4})、Tani's algorithmを使う量子計算ではO(p^{1/6})。(2) 同種写像経路に対するmeet-in-the-middle攻撃：古典計算ではO(p^{1/4})で、SSIPと同じです。(3) 特定の構造を利用した攻撃に対する多項式時間アルゴリズム（van Oorschot-Wiener）：SIDHには適用できません。数十本の論文がSIDHの安全性を分析しましたが、11年間にわたって古典・量子のいずれでも多項式時間攻撃は見つかりませんでした。この実績により、SIKEは信頼できるNIST最終候補となりました。最終的な破りはSSIPへの直接攻撃ではなく、SIDHが公開する補助トーション点情報の悪用によってもたらされました。

2022年7月30日、Wouter CastryckとThomas Decruは、SIDHに対する多項式時間の古典攻撃を示すプレプリントを公開しました。この攻撃は、SIDHの補助トーション点phi_A(P_B), phi_A(Q_B)に含まれる追加情報を利用します。この情報により、実質的に3^b-トーション部分群上のphi_Aの作用が明らかになります。これを像曲線E_Aと組み合わせると、複素乗法を持つ楕円曲線の理論とRichelot同種写像の技法を使って、phi_Aの核、ひいてはphi_A自体を復元できます。この攻撃は、128ビットのポスト量子安全性を提供するはずだったSIKEp434に対して、ノートパソコン上で62分で実行されました。数日以内に、独立した研究者たちがすべてのSIDHパラメータへの攻撃を確認し、拡張しました。

SIDHの設計では、双方が秘密の同種写像による相手側のトーション基底点の像を公開する必要がありました。これはプロトコルを動作させるために必要でした。phi_A(P_B)とphi_A(Q_B)がなければ、Bobは自分の同種写像をAliceの曲線へ移して共有秘密を計算できないためです。しかし、この追加情報は3^b-トーションに制限したphi_Aの作用を明らかにするものであり、予想をはるかに超える、壊滅的な量の情報を提供することが判明しました。Castryck-Decru攻撃は、種数2の曲線（Richelot同種写像）を使って問題をより高い種数の対象へ持ち上げます。そこでは、制限された作用だけでphi_Aが完全に決定されます。この情報漏洩はSIDHの構造に組み込まれているため、プロトコルの基本設計を変更せずに修正することはできません。

2022年7月5日（Castryck-Decru攻撃の前）、NISTはPQC標準化に向けた初期の選定結果を発表していました。選定されたのはML-KEM (Kyber)、ML-DSA (Dilithium)、SLH-DSA (SPHINCS+)、FN-DSA (Falcon)であり、SIKEは含まれていませんでした（SIKEは第2ラウンドで検討されていました）。2022年7月のCastryck-Decru攻撃により、NISTはSIKEを検討対象から正式に除外しました。NISTは「SIKEは標準化の検討対象ではなくなりました」と発表しました。これはNIST PQC競争における最も劇的な暗号解読上の展開でした。11年間の分析を生き延びた方式でさえ、まったく新しい数学的洞察によって破られ得ることを示したのです。

Castryck-Decru攻撃から1週間以内に、Thomas DecruとLuciano Mainoがそれぞれ独立に、続いてDamien Robertがさらなる改良を発表しました。Robertによる攻撃の変種は同じ洞察を利用しますが、同種写像の核を直接計算するのではなく、E_Aのエンドモルフィズム環を計算します。そのため、数学的な説明はより簡潔だとも考えられています。こうした迅速な独立再発見は、Castryck-Decru攻撃が特殊な技巧ではなく、SIDHの根本的な構造上の弱点を特定したことを裏付けました。後続論文がすぐに発表されたことは、多くの研究者がSIDHのトーション点情報漏洩を潜在的な攻撃経路として研究していたことも反映しています。研究者たちはそれが異例の情報開示であると認識していましたが、CastryckとDecruが種数2への橋渡しを見つけるまで、それを悪用できなかったのです。

FESTA（Fast Encryption from Supersingular Torsion Attacks、2023年）は、SIDHに着想を得つつ、トーション点の補助データを回避するKEM設計です。FESTAは異なるプロトコル構造を使用します。公開鍵には相手のトーション基底の像を含めず、秘密の同種写像は像曲線だけによってコミットされます（補助点はありません）。FESTAは、構造に関する情報の漏洩を抑える方法で同種写像を使って暗号化します。初期の安全性分析では、FESTAはCastryck-Decru攻撃の構造を回避すると示唆されています。ただし、FESTAはより新しく、SIKEが11年間にわたって受けてきた検証ほどの精査を受けていません。そのため、同種写像コミュニティは、十分な分析を経る前に新しい方式を実運用へ導入することに慎重です。

SIKEが破られたことから、重要な教訓が得られます。(1) 補助情報の開示は危険です。SIDHの追加トーション点データはプロトコルに必要でしたが、情報を致命的に漏洩させました。プロトコル設計者は主要な値だけでなく、公開されるすべてのデータを分析する必要があります。(2) 実績は安全性の証明ではありません。既知の攻撃が11年間なかったことは安心材料ですが、保証ではありません。暗号学的証明（明確に定義された困難問題への帰着）の方が、権威への依存や精査を生き延びたという実績よりも信頼できます。(3) 新しい数学的ツールはリスクを生みます。Castryck-Decru攻撃では、同種写像暗号解析にこれまで適用されていなかった数学分野の道具である種数2のRichelot同種写像が使われました。新しいプリミティブを調査する暗号解読者は、新たな数学領域も考慮しなければなりません。

SIKEが破られた後も、同種写像ベース暗号は研究分野として存続しています。SQISign署名（Level 1で177バイト）は、現在知られているPQC署名の中で最もコンパクトなものとして残っており、SIDH攻撃の影響を受けない異なる困難性仮定（エンドモルフィズム環問題）を使用します。CSIDHベースのプロトコルは、トーション点の漏洩がない類群作用構造（可換な同種写像）を使用しますが、CSIDHにも固有の課題があります（かつてのSIDHより遅く、量子安全性の分析が継続中です）。同種写像コミュニティは、SIKEが破られたことを学習の機会と捉えています。この経験によって、同種写像プロトコルでどの情報を隠す必要があるのかについての理解が深まり、将来の方式設計に役立つ知識が得られました。

SIDHのどの設計要素によって、Castryck-Decru攻撃が可能になりましたか？

SIDHは、2^aと3^bの同種写像チェーンを2者間で交互にたどり、鍵交換を可能にするために補助トーション点の像を共有します。SIKEはFujisaki-Okamotoを使ってSIDHをCCA2安全にします。SIKEはNIST PQC候補の中で最小の鍵（374バイト）を持っていましたが、処理速度は100～1000倍遅いものでした。11年間安全性が保たれた後、Castryck-Decruは2022年7月、種数2のRichelot同種写像を使ってトーション点の漏洩を悪用し、SIKEを破りました。NISTはSIKEを除外しました。FESTAはトーション点の開示を回避します。SQISignはエンドモルフィズム環の困難性を利用して研究が続けられています。SIKEが破られたことは、補助的に公開されるデータを主要なプロトコル値と同じように慎重に分析しなければならないことを示しています。