同種写像暗号に対する量子および古典的攻撃の最新動向：SIDH/SIKEの事例から学ぶ
はじめに
量子コンピュータの能力向上は、既存の公開鍵暗号システムにとって深刻な脅威となります。Shorのアルゴリズムに代表される量子アルゴリズムは、素因数分解問題や離散対数問題といった、現在の主要な公開鍵暗号の安全性の根拠となる数学的困難性を効率的に破ることができます。このような背景から、ポスト量子暗号（PQC）の研究開発が活発に進められてきました。PQCの候補として、格子ベース、ハッシュベース、符号ベース、多変数多項式ベース、そして同種写像ベースの暗号が挙げられていました。
同種写像ベース暗号は、超特異楕円曲線の間の同種写像グラフ上の探索問題や、特定の同種写像を構成する問題といった数学的困難性に基づいています。これらの問題は、既知の量子アルゴリズムによっては効率的に解けないと考えられていたため、特に耐量子性が高いと評価されていました。Supersingular Isogeny Diffie-Hellman (SIDH) や、それに基づく鍵カプセル化機構である Supersingular Isogeny Key Encapsulation (SIKE) は、コンパクトな鍵サイズと耐量子性から、PQC標準化プロセスの第3ラウンドまで進んでいました。
しかし、近年、SIDH/SIKEに対して驚異的な古典的攻撃アルゴリズムが発見され、その安全性評価は根本的に覆されました。本稿では、同種写像暗号に対する量子的な攻撃の可能性に関する従来の理解を確認しつつ、SIDH/SIKEを破綻させた最新の古典的攻撃手法の技術的詳細に深く踏み込みます。そして、この破綻がPQC研究、特に同種写像ベース暗号分野に与える影響と今後の展望について考察します。
同種写像暗号の基礎と量子攻撃の可能性
同種写像暗号は、楕円曲線の間の代数的な写像である「同種写像」を利用します。特に、超特異楕円曲線を利用したスキームが多く研究されています。超特異楕円曲線 $E_1, E_2$ が与えられたとき、それらの間の同種写像 $\phi: E_1 \to E_2$ で、ある有限群 $K$（同種写像の核）を持つものは、古典的にはVéluの公式などを用いて計算することができます。
SIDHは、Diffie-Hellman鍵交換の同種写像版と見なすことができます。アリスとボブは共有されたベースとなる超特異楕円曲線 $E_0$ と、異なる素数 $p_A, p_B$ を準備します。アリスは秘密の $p_A$-isogeny $\phi_A: E_0 \to E_A$ を、ボブは秘密の $p_B$-isogeny $\phi_B: E_0 \to E_B$ を計算します。それぞれの秘密鍵に対応する同種写像の終点曲線 $E_A$ と $E_B$ を公開します。その後、アリスはボブの公開した曲線 $E_B$ に対して自分の秘密鍵に対応する同種写像を適用し $\phi_A': E_B \to E_{AB}$ を計算します。同様に、ボブはアリスの公開した曲線 $E_A$ に対して自分の秘密鍵に対応する同種写像を適用し $\phi_B': E_A \to E_{BA}$ を計算します。秘密鍵の選び方により、$E_{AB}$ と $E_{BA}$ は同型となり、この同型写像を計算することで共有鍵を導出します。このスキームの安全性は、公開された曲線 $E_A, E_B$ から秘密の同種写像 $\phi_A, \phi_B$ を復元することの困難性に基づいています。
同種写像問題に対する量子アルゴリズムとしては、Childs, Jao, Plutによる量子アルゴリズムが知られています。このアルゴリズムは、特定の条件下（例えば、核の群がサイクリックである場合）で、同種写像の核を効率的に見つけることができます。しかし、SIDH/SIKEでは、核の群が直積の形 ($(\mathbb{Z}/p_A^a \mathbb{Z}) \times (\mathbb{Z}/p_A^a \mathbb{Z})$ など) である場合や、秘密鍵から生成される同種写像の核が固定されていない場合など、これらの既知の量子アルゴリズムが直接的に効率的な攻撃に結びつかないように設計されていました。そのため、SIDH/SIKEはShorタイプの量子アルゴリズムには耐性があると考えられており、特に量子コンピュータによる大規模な鍵探索（Groverタイプの攻撃）に対しては、鍵長を適切に設定することで対応可能であると評価されていました。つまり、SIDH/SIKEの主な脅威は、同種写像問題に対する未知の効率的な量子アルゴリズムの出現であると考えられていたのです。
SIDH/SIKEを破綻させた古典的攻撃
2022年夏、SIDH/SIKEに対する驚異的な古典的攻撃アルゴリズムが立て続けに発表されました。まず、CastryckとDecruによる論文が公開され、SIDHの鍵交換プロトコルにおける秘密鍵（同種写像の核）を、補助点を用いることなく、公開情報（終点曲線）から古典コンピュータを用いて効率的に復元できることが示されました。その直後にはRobertによるより一般化された攻撃、さらにLu, Petit, YuanによるSIDH鍵カプセル化メカニズムに対する具体的な攻撃手法が示されました。
Castryck-Decru攻撃の核心は、SIDHで用いられる同種写像の構成法に潜む特定の代数構造を利用した点にあります。SIDHでは、秘密の核を持つ同種写像を効率的に計算するために、特定の性質を持つ補助点（torsion points）を利用します。攻撃者は、公開された終点曲線上のこれらの補助点の情報を利用して、秘密の同種写像の核を特定しようと試みます。
CastryckとDecruの攻撃は、SIDHの公開鍵である終点曲線 $E_A$ (または $E_B$) と、その曲線上の特定の位数を持つ点（例えば、SIDHのパラメータで定められた位数 $p_B^b$ の点）を利用します。彼らは、終点曲線 $E_A$ 上の位数 $p_B^b$ の点が、ベース曲線 $E_0$ 上の点にアリスの秘密の同種写像 $\phi_A^{-1}$ を適用した像であることを利用しました。攻撃のポイントは、特定の点のx座標が、秘密の同種写像の核を特徴づける多項式の根となるような関係式を見出したことです。より具体的には、Véluの公式の分子多項式の根と、終点曲線上の点のx座標との間に、秘密の核に依存する特定の代数的な関係が存在することを利用します。Castryck-Decruの攻撃は、この関係式を利用して、終点曲線上の特定の位数を持つ点のx座標から、秘密の同種写像の核を効率的に計算することを可能にしました。この攻撃は、サイドチャネル攻撃ではなく、公開情報のみに基づいています。
この古典的攻撃により、SIDHの秘密鍵の探索空間が劇的に縮小され、数分から数時間といった実用的な時間で秘密鍵が計算可能であることが示されました。これは、SIDH/SIKEが安全性の根拠としていた数学的困難性が、古典コンピュータ上でも想定より遥かに容易に解けることを意味します。
セキュリティ上の含意と今後の展望
SIDH/SIKEに対する古典的攻撃の成功は、ポスト量子暗号の研究コミュニティに大きな衝撃を与えました。SIDH/SIKEはPQC標準化プロセスの最終ラウンドまで進んでいた候補であり、多くの研究者や開発者がその実装に取り組んでいました。この破綻により、SIDH/SIKEは標準化候補から除外されることとなりました。
この出来事の重要な教訓の一つは、量子コンピュータが登場する前に、古典コンピュータによる暗号解読技術も進化し続けるという現実です。耐量子暗号の評価は、量子アルゴリズムに対する耐性だけでなく、既存および将来の古典的攻撃手法に対する耐性も同時に、かつ継続的に評価されるべきであることを改めて示しました。
一方で、同種写像ベース暗号の研究開発が完全に終わったわけではありません。SIDH/SIKEの破綻は、その特定の構成（特に、補助点を用いた秘密鍵の計算と、その結果として公開される終点曲線の構造）に起因するものであり、同種写像問題一般の困難性や、他の同種写像ベーススキームの安全性に直接影響を与えるものではありません。例えば、Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) は、SIDHとは異なる数学的構造に基づいており、現状ではCastryck-Decruタイプの攻撃には耐性があると考えられています。CSIDHは、SIDHに比べて鍵サイズが大きいという欠点がありますが、新しい同種写像ベースのPQC候補として引き続き研究されています。
今後の同種写像暗号の研究は、SIDH/SIKEの破綻原因を深く分析し、同様の脆弱性を持たない新しい構成を探求する方向へと進むでしょう。また、サイドチャネル攻撃やフォルト攻撃といった実装上の脅威に対する耐性の研究も、引き続き重要です。同種写像計算の効率化と、鍵サイズや計算コストの削減も、実用化に向けた重要な課題となります。
結論
本稿では、同種写像暗号、特にSIDH/SIKEに対する量子および古典的な攻撃の動向について技術的な観点から分析しました。SIDH/SIKEは、既知の量子アルゴリズムに対して耐性があると評価され、PQCの有力候補と見なされていましたが、2022年に発見された効率的な古典的攻撃により、その安全性は否定されました。この出来事は、PQCの評価において、量子脅威のみならず、古典的攻撃の継続的な進化も考慮に入れることの重要性を示しています。
同種写像ベース暗号の研究は、SIDH/SIKEの破綻を乗り越え、新たな安全な構成の探求へと進んでいます。CSIDHのような他のスキームや、全く新しいアイデアに基づく同種写像暗号の研究が、ポスト量子時代における多様な暗号技術の選択肢を提供し続けることが期待されます。サイバーセキュリティ研究者や技術者にとって、このような最新の攻撃手法の詳細を理解し、将来の脅威に対する備えを進めることは、極めて重要であると言えます。