楕円曲線の同種写像：数学的基礎

体 k 上の2つの楕円曲線 E と E' の間の同種写像は、非定数有理写像 phi: E -> E' であり、同時に群準同型でもあります。つまり、Eの群演算をE'の群演算へ写します。すべての同種写像 phi には双対同種写像 phi_hat: E' -> E が存在し、phi_hat と phi の合成は、E上の multiplication-by-deg(phi) に等しくなります。同種写像の次数は核の大きさです。次数lの同種写像の核の大きさはlです。同種写像はスカラー倍を一般化したものです。n倍写像は、EからE自身への次数n^2の同種写像です。有限体上の同種写像は有理関数（多項式）として計算され、効率的に評価できます。

Veluの公式（1971年）は、Eの部分群Gが与えられたときに、同種写像 phi: E -> E/G を計算するための明示的な公式です。像曲線 E/G = E' と有理写像 phi は、Gによって完全に決まります。Veluの公式では、像曲線の係数と有理写像を、次数が|G|に等しい有理関数として計算します。素数位数lの核部分群Gの場合、同種写像の次数はlであり、O(l)回の演算で計算できます。sqrt-Veluアルゴリズム（Bernstein et al., 2019）は、大きなlに対してこの計算量をO(sqrt(l))回の演算まで削減し、CSIDHで効率的な大きな素数次数の同種写像を利用できるようにしました。Veluの公式は、同種写像ベース暗号全体の計算上の中核です。

有限体 Fp 上の楕円曲線は、同種写像グラフとして整理できます。頂点は楕円曲線のj不変量です。これは曲線を同型を除いて決定する標準的な不変量です。辺はl-同種写像です。小さな素数lに対して、各通常曲線からは、l-捩れ部分群の構造により、ちょうどl+1本の出次数l-同種写像が存在します。Fp上のl-同種写像グラフは、(l+1)-正則グラフです。これらのグラフが持つラマヌジャン性（エキスパンダーグラフとしての性質）により、グラフ上のランダムウォークは速やかに混合します。これが同種写像ベース暗号の基盤となる困難性の仮定を提供します。長さO(log p)のランダムウォークによって、j不変量上の一様分布が生成されます。

Fp上の楕円曲線は、2つのカテゴリーに分かれます。通常曲線は自明でないp-rankを持ちます。つまり、p^2個の同型類が存在し、火山構造（火口と斜面）を持つ複雑な同種写像グラフを形成します。超特異曲線はp-rankが0であり、Fp2上の単一の連結した同種写像グラフにすべて存在します。Fp上の超特異j不変量の数は、およそp/12です。SIDHとSIKEは、強い拡張性を持つラマヌジャングラフであり、ランダムウォークの方向を明らかにする可能性のある火山構造を持たないため、超特異曲線を使用します。CSIDHも超特異曲線を使用しますが、Fp2ではなくFp上で使用し、異なる代数構造を活用します。

同種写像ベース暗号は、関連する2つの困難な問題に基づいています。Supersingular Isogeny Problem（SSIP）は、Fp2上の2つの超特異楕円曲線 E と E' が与えられたときに、phi: E -> E' となる同種写像を求める問題です。Computational Supersingular Isogeny（CSSI）問題は、E、E' = phi(E)、および phi の次数が与えられたときに、phiを求める問題です。SSIPに対する最良の古典アルゴリズムはO(p^{1/4})時間で動作します。最良の量子アルゴリズム（Taniのclaw-finding）はO(p^{1/6})時間で動作します。p = 2^{434}の場合、これは128ビットの古典安全性に相当します。これは、RSA/ECCに対するShorのアルゴリズムの指数関数的な高速化と比べて、量子計算による高速化が大幅に小さいため、同種写像ベース方式は耐量子安全であると考えられます。

SIDH（Supersingular Isogeny Diffie-Hellman）は、p = 2^a * 3^b - 1 という特殊な構造の素数を使用します。これにより、Fp2上の曲線 E に2^a-捩れ点（2^a * P = 0を満たす点Pの集合）と、利用可能な3^b-捩れ点が存在することが保証されます。Aliceの秘密は、2^a-捩れ部分群のランダムな要素が生成する核を持つ2^a-同種写像 phi_A: E -> E_A です。Bobの秘密は、3^b-同種写像 phi_B: E -> E_B です。両者は捩れ点の像を交換します。Aliceは E_A と phi_A(P_B)、phi_A(Q_B) を公開します。Bobは E_B と phi_B(P_A)、phi_B(Q_A) を公開します。これにより、各当事者は相手の曲線から同種写像を計算でき、同じ共有j不変量に到達します。

楕円曲線の自己準同型環 End(E) は、EからE自身へのすべての同種写像（スカラー倍を含む）からなる環です。Fp上の通常曲線の場合、End(E)は虚二次体のオーダーです。超特異曲線の場合、End(E)はpと無限遠点で分岐する四元数代数の極大オーダーです。End(E)の構造によって、曲線は同型を除いて完全に決まります。自己準同型環問題、つまりEが与えられたときにEnd(E)を計算する問題は、困難であると考えられています（超特異曲線の場合はSSIPと同等です）。Castryck-Decru攻撃は、SIDHプロトコルから漏洩した追加情報を利用して自己準同型環の一部を効率的に再構成し、方式を破りました。

次数lの同種写像 phi: E -> E' は、次数lの多項式として表現できます。点の逆元が同じx座標を持つことを利用した対称性最適化を行えば、次数l/2の多項式として表現することもできます。Veluの公式を使って特定の点Pに対する phi(P) を計算するには、O(l)回の乗算が必要です。l = 2^a が約2^216であるSIDHでは、これは実用的でないように見えます。しかしSIDHでは、2^a-同種写像をa個の個別の2-同種写像の連鎖に分解できることを利用します。各2-同種写像は低コストであり、a段階の連鎖によって2^a-同種写像が得られます。3^bの場合も同様です。sqrt-Veluにより、CSIDHでは大きな奇素数次数の同種写像を、O(l)ではなくO(sqrt(l))で計算できるため、CSIDHが実用的になります。

SIKE（Supersingular Isogeny Key Encapsulation）はNIST PQC候補であり、第4ラウンドで破られるまで、すべてのラウンドを勝ち残っていました。SIKEは、NIST候補の中で最小の鍵サイズを実現した点で注目されました。SIKEp434（NIST Level 1）の鍵は374バイトです。比較すると、ML-KEM-512の公開鍵は800バイトです。SIKEがこのコンパクトさを実現できたのは、共有秘密が単一のj不変量（約430ビットの体要素）から導出されるためです。しかし、このコンパクトさには代償があり、SIKEは他の候補より100～1000倍遅い方式でした。CastryckとDecruが2022年7月、ラップトップ上で数分で実行できる古典攻撃によってSIKEを破ると、SIKEはNISTコンペティションから直ちに除外されました。

同種写像ベース暗号は、ポスト量子暗号のアプローチの中で独自の位置を占めています。鍵サイズは、格子暗号（ML-KEM：800バイト以上）やハッシュベース署名（SLH-DSA：公開鍵は32～49バイトですが、署名は7856～49856バイト）よりも大幅に小さくなります。性能はすべての代替方式より低速で、SIKEはML-KEMより100～1000倍遅い方式でした。安全性の仮定は、ML-KEM/ML-DSAで使用されるLWE、SIS、ハッシュ関数とは異なり、暗号学的多様性を提供します。耐量子安全性の基盤となる同種写像経路問題には、既知の多項式時間量子アルゴリズムがありません。これは、Shorのアルゴリズムによって完全に破られるRSA/ECCとは異なります。SIKEが古典計算で破られたことは、十分に研究されているLWE問題とは異なり、同種写像の困難性がまだ解明途上にあることを示しています。

SIKEが破られた後も、同種写像ベース暗号は活発な研究分野であり続けています。SQISign（Short Quaternion and Isogeny Signature）は177バイトの署名を持つ同種写像ベースの署名方式です。これはLevel 2で2420バイトのML-DSAと比べて小さく、既知のPQC署名として最小です。SQISignは、与えられた2つの超特異曲線の間で所定の次数の同種写像を計算するという困難な問題を使用します。この問題は、自己準同型環問題として定式化されています。FESTA（Fast Encryption from Supersingular Torsion Attacks）は、SIDHを脆弱にした捩れ点に関する追加の補助データを必要としない、新しいKEM設計です。CTIDH（Constant-Time CSIDH）はCSIDHの性能を改善します。これらの方式により、SIKEが排除された後も同種写像の研究は重要であり続けています。

楕円曲線間の同種写像とは何ですか。

同種写像は、群準同型である有理写像 phi: E -> E' であり、その次数は核の大きさに等しくなります。Veluの公式は、核部分群から像曲線と写像を計算します。同種写像グラフでは、曲線を頂点として整理し、l-同種写像を辺とする(l+1)-正則ラマヌジャングラフを形成します。超特異曲線（SIDH、SIKE、CSIDHで使用されます）の同種写像グラフは、強い拡張性を持ちます。SSIPとCSSIの問題が、同種写像の安全性の基盤となっています。SIDHは捩れ点の構造を利用し、2-同種写像と3-同種写像を交互に連結します。自己準同型環の計算はSSIPと同等です。SQISignとFESTAは、自己準同型環問題の困難性を利用する、SIKE後の活発な研究分野を代表する方式です。