CSIDH：可換超特異同種写像

CSIDH（Commutative Supersingular Isogeny Diffie-Hellman、Castryck et al., 2018）は、SIDHのトーション点漏洩を、根本的に異なる代数構造を使うことで完全に回避する同種写像ベースの鍵交換方式です。CSIDHは、SIDHのようにFp2上ではなく、Fp上の超特異曲線を扱います。安全性の仮定は類群作用の可換性です。2者がそれぞれ共通の開始曲線に秘密の類群要素を作用させ、可換性によって両者が同じ共有曲線に到達します。補助的なトーション点情報は一切公開されず、公開鍵は単一のj不変量だけです。この設計は、SIDHに対するCastryck-Decru攻撃を乗り越えました。

p = 3 mod 4を満たすFp上では、超特異曲線Eは特別なエンドモルフィズムpi（フロベニウス）を持ち、そのエンドモルフィズム代数には虚二次整環Z[pi]が含まれます。イデアル類群Cl(Z[pi])は、Fp上の超特異曲線の集合（同型を除く）に自由かつ推移的に作用します。Cl(Z[pi])内のイデアルaは、曲線Eに作用して新しい曲線a * Eを生成します。これは、E[a]をイデアルaに対応するトーション部分群とする曲線E/E[a]として計算されます。この作用は可換であり、a * (b * E) = b * (a * E) = [ab] * Eが成り立ちます。これがCSIDHの群作用であり、Diffie-Hellmanの可換版を実現します。

CSIDH鍵交換は次のように進みます。公開パラメータ：Fp上の超特異曲線E0と、小さな奇素数l_1, ..., l_n。秘密鍵：Aliceは各a_iを{-m, ..., m}内のランダムな小整数としてa = (a_1, ..., a_n)を選びます。Bobはb = (b_1, ..., b_n)を選びます。Aliceの公開鍵：E_A = [l_1^a_1 * ... * l_n^a_n] * E0。Bobの公開鍵：E_B = [l_1^b_1 * ... * l_n^b_n] * E0。共有秘密：AliceはE_Bに自分の秘密指数を適用し、BobはE_Aに自分の秘密指数を適用します。可換性により、両者はE_AB = [product(l_i^(a_i + b_i))] * E0を得ます。共有秘密はj(E_AB)です。補助点は公開されません。

CSIDHのリファレンス実装では、p = 4 * l_1 * l_2 * ... * l_74 - 1を使用します。ここでl_1からl_74は最初の74個の奇素数（3, 5, 7, ..., 373）です。これによりpは約512ビットになります。各秘密鍵成分a_iは{-5, ..., 5}（各成分11通り、成分数74）に含まれます。類群の位数はおよそsqrt(p)で、鍵空間のサイズは11^74です。各同種写像ステップでは、素数l_iごとにl_i-トーション部分群を見つけ、Velu公式を使ってl_i-同種写像を計算します。sqrt-Veluを使うと、各大きな素数に対する同種写像ステップはO(sqrt(l_i))回の演算で実行できます。鍵交換全体にかかる時間は、最新のハードウェア上でCSIDH-512の場合およそ1～5ミリ秒です。

元のCSIDHは定時間（constant-time）ではありません。Veluステップの回数が秘密鍵の値a_iに依存するため、タイミングサイドチャネルを通じて情報が漏洩します。CTIDH（Constant-Time ISOGENY Diffie-Hellman、Bernstein et al., 2021）は、固定重み鍵形式と、注意深く設計された定時間の同種写像計算を使ってこの問題を解決します。CTIDHの秘密鍵は、絶対値の合計が固定されたベクトルに制限されます（例：sum |a_i| = 130）。同種写像の計算は秘密鍵の値にかかわらず固定回数のステップで進み、秘密指数が0のステップにはダミーの同種写像計算を使って処理を埋めます。CTIDHはCSIDH-512と同程度の安全性を実現しながら、組み込み環境への導入に適した厳密な定時間保証を提供します。

CSIDHの量子安全性は、格子ベース方式の場合よりも複雑です。最良の量子攻撃は、隠れシフト問題に対するKuperbergのアルゴリズム（2005年）を使用します。この攻撃は、準指数時間L(1/2) = exp(O(sqrt(log p)))で類群作用の構造を破ります。これは、古典計算機に対する最良の攻撃であるsqrt(p)よりも大幅に優れているため、量子コンピューターによってCSIDHは古典的な攻撃者を想定した場合よりも大きく安全性が低下します。128ビットの耐量子安全性（L(1/2)攻撃に対して）を実現するには、CSIDHでは約5000ビットの素数p（CSIDH-5000）が必要です。これは、128ビットの古典安全性に必要な512ビットと比較して大きな値です。CSIDH-512の量子安全性はわずか62～72ビットと推定され、NIST Level 1の要件を大きく下回ります。

CSIDHの安全性は、群作用逆問題（GAIP）に依存しています。これは、E_A = a * E0とE0が与えられたときにaを求める問題です。既知の最良のアルゴリズムは、Pohlig-Hellmanに類似した還元とbaby-step-giant-stepを組み合わせたもので、古典計算機ではO(sqrt(|Cl|)) ~ O(p^{1/4})の計算量で実行されます。量子計算機に対する困難性はKuperbergアルゴリズムによって評価され、CSIDHはLWEベースの方式よりも量子安全性が低くなります。LWEに対する最良の量子攻撃である格子ふるい法は、より保守的な安全性余裕をもたらします。CSIDHの利点はコンパクトさです。CSIDH-512の公開鍵は64バイト（j-不変量のみ）であり、ML-KEM-512の800バイトと比べて小さくなっています。可能な限り小さい鍵を必要とし、量子安全性の余裕が小さくなることを受け入れられる用途では、CSIDHは依然として興味深い方式です。

CSIDHの量子安全性に関する制限に対処するため、いくつかの派生方式が提案されています。BSIDH（Bは「better」の意）は、より高次数の基底曲線と楕円曲線の積を使用し、計算速度を維持しながら類群のサイズを大きくします。Csurf（CSIDH on the surface）は、異なる超特異曲線の集合を扱うことで、より高速な群作用の計算を可能にします。高種数CSIDHの提案では、Fp上の種数2曲線のヤコビアンを使用し、より大きな群作用空間を提供することで、量子安全性の余裕を改善できる可能性があります。これらの派生方式はいずれも広く採用されたり、NISTで検討されたりする段階には至っていません。その一因は、CSIDH派生方式の量子安全性に関する分析が現在も進展中であり、格子ベース方式ほど成熟していないことにあります。

CSIDHとSIDHは、基本的な点で異なります。可換性：CSIDHは可換な群作用（類群）を使用します。一方、SIDHは補助ねじれ点を伴う非可換な同種写像を用いた非対話鍵交換です。基礎体：CSIDHはFp上で動作し、SIDHはFp2（2次拡大体）上で動作します。公開鍵サイズ：CSIDHはFp上の単一のj-不変量で64バイトですが、SIDHは曲線と2つのFp2点を含み、324バイト以上です。安全性：CSIDHはCastryck-Decru攻撃を乗り越えましたが、SIDHは破られました。量子安全性：CSIDHで128ビットの量子安全性を実現するには5000ビットの素数が必要です。SIDHは古典的な破り方が発見される前には、これに匹敵する量子耐性を備えていました。性能：CSIDH-512は約1～5ミリ秒です。SIDHも同程度でしたが、CSIDH-5000ははるかに低速になります。

CSIDHの可換性により、非対話鍵交換（NIKE）が可能になります。AliceはE_A = a * E0を公開し、BobはE_B = b * E0を公開します。その後、追加の通信を行わなくても、どちらの公開鍵からでも共有秘密を計算できます。Aliceはa * E_B = a * (b * E0) = ab * E0を計算し、Bobはb * E_A = b * (a * E0) = ab * E0を計算します。このNIKEの性質は、対話的な鍵交換が現実的でない用途で有用です。たとえば、送信者と受信者が同時にオンラインにならないメール暗号化などが該当します。CSIDHによるNIKEは、耐量子性を備えたDiffie-Hellman NIKEに相当します。LWEに基づくML-KEMは、追加のプロトコル設計なしにNIKEを自然にサポートすることはできません。

CSIDHは標準化されておらず、実運用システムにもまだ導入されていません。CSIDHは活発な研究対象であり、実装も利用できます。たとえば、CTIDH（constant-time）、csidh-reference（教育用のPython実装）、supersingular-isogeny-toolbox（最適化されたC実装）があります。導入における最大の障壁は量子安全性です。CSIDH-512の量子安全性は62～72ビットと推定され、NIST Level 1（128ビット）を下回るため、NIST準拠を必要とする耐量子アプリケーションには適していません。CSIDH-5000なら安全性の基準を満たしますが、速度は大幅に低下します。量子安全性の分析を改善する研究や、この差を埋める派生方式の研究は続いていますが、2024年時点でCSIDHは導入可能な暗号プリミティブではなく、研究用プロトタイプにとどまっています。

CSIDHは、フロベニウス自己準同型piに対応するCl(Z[pi])の可換な類群作用を、Fp上の超特異曲線に対して使用します。公開鍵は単一のj-不変量（64バイト）です。補助ねじれ点を公開しないため、SIDHの脆弱性を回避できます。類群作用は可換であり、NIKEを可能にします。古典的な最良攻撃の計算量はO(p^{1/4})です。量子的な最良攻撃であるKuperbergのアルゴリズムは、準指数時間L(1/2)で実行され、128ビットの量子安全性には5000ビットの素数が必要です。CTIDHはconstant-time実装を提供します。CSIDH-512の量子安全性は約65ビットにすぎません。CSIDHは標準化されておらず、研究は、コンパクトな鍵を維持しながら量子耐性を向上させる派生方式に重点を置いています。