同種写像ベース暗号の未来

2022年7月にCastryck-DecruがSIKEを破ったことで、同種写像分野は大きく変化しました。その発表以前、同種写像ベース暗号は、小さな鍵サイズ、活発な標準化活動、拡大する研究コミュニティを備えた有望な耐量子暗号の方向性でした。SIKEの破綻後、この分野は基盤を再検討せざるを得なくなりました。重要な問いは、新たなRichelot同種写像技法が登場した後も、同種写像ベース暗号のどの側面が困難なままなのかということです。現時点での答えは、自己準同型環に基づく困難性（SQISignで使用）と可換な類群作用（CSIDH）は依然として安全性を保っているというものです。破られたのはSIDHに固有の補助ねじれ点からの漏えいであり、同種写像全般ではありません。

SQISign（Short Quaternion and Isogeny Signature、De Feo et al.、2020年）は、既知の中で最もコンパクトな耐量子署名方式です。公開鍵は64バイト（超特異j-不変量）で、署名はLevel 1で177バイトです。比較として、ML-DSA（Dilithium）はLevel 2で公開鍵が1312バイト、署名が2420バイトです。SQISignの安全性はDeuring対応に基づいています。これは、与えられた2つの超特異曲線の間で指定された次数の同種写像を計算する問題が、自己準同型環の四元数代数内でイデアルを見つける問題と同値であることを利用します。SQISignは、この困難な問題に対するFiat-Shamir識別方式を使用し、応答となる同種写像を圧縮表現することで署名を生成します。

SQISignのコンパクトさには、深刻な性能上のコストが伴います。署名生成では、四元数代数においてイデアルから同種写像への変換を使い、次数の大きい同種写像（約p^{1/4}）を計算する必要があります。これは計算負荷の高い処理であり、パラメーターセットによって異なりますが、デスクトップCPUで約60～600秒かかります。検証はより高速（約200ミリ秒）ですが、それでもML-DSAの検証（マイクロ秒単位）よりはるかに低速です。SQISign 2.0（2023年）はアルゴリズムの改良により性能を100倍向上させ、署名生成時間を1～10秒に短縮しました。SQISign HD（high degree）などの派生方式でも最適化が続けられています。主な対象用途は、帯域幅が極端に制約され、計算速度が二次的となるユースケースです。たとえば、IoT証明書、ブロックチェーンデータ、宇宙通信などが挙げられます。

FESTA（Fast Encryption from Supersingular Torsion Attacks、2023年）は、SIDH型のねじれ点漏えいを明確に回避するよう設計されたKEMです。設計上の重要な着想は、SIDHのようにphi_A(P_B)とphi_A(Q_B)を公開するのではなく、暗号化側の公開鍵を像曲線だけにする、つまりねじれ点の像を含めない、異なる同種写像構造を使用することです。FESTAは2^n-同種写像を変更された方法で使用し、相手側のねじれ基底の像がなくても復号できるようにします。初期分析では、補助情報の構造が異なるため、FESTAはCastryck-Decru攻撃に耐性があることが示唆されています。FESTAは有望な方向性ですが、さらなる暗号解析による検証が必要です。SIKEが予想外に破られたことを受け、同種写像コミュニティは慎重な姿勢を取っています。

SCALLOP（Scalable Commutative Actions with Large Oriented Primes、2023年）は、CSIDHの量子安全性の弱点に対処します。CSIDHで使用される小さな素数p = 512ビットでは、Kuperbergの準指数アルゴリズムに対して量子安全性が約65ビットにしかなりません。SCALLOPは異なる代数構造を使用します。すなわち、大きな虚二次整環による複素乗法を持つ曲線を用い、類群をKuperberg型の量子攻撃に耐えるよう特別に設計します。SCALLOPは、CSIDH-5000より小さいパラメーターサイズで128ビットの量子安全性を提供する、より大きな実効類群を実現します。その代償として、SCALLOPの代数的な構成はより複雑であり、CSIDHほど多くの独立した分析を受けていません。

同種写像方式には、SQISignの177バイトの署名やCSIDHの64バイトの鍵に見られる独自のコンパクトさがあり、格子方式とは異なる困難性の仮定に基づいています。そのため、多層防御を実現するハイブリッド構成では、同種写像と格子の要素を組み合わせます。ハイブリッドKEMの例では、ML-KEM-512とCSIDH-512の両方でカプセル化し、2つの秘密をまとめてハッシュします。結合された鍵を破るには、ML-KEM（LWEの困難性）とCSIDH（類群作用）の両方を同時に破る必要があります。いずれか一方が破られていなければ、ハイブリッド方式は安全です。この暗号アジリティのアプローチは、単一の耐量子暗号プリミティブを超える追加の保証を求める組織に対して、NISTとNSAが推奨しています。特に、量子コンピューターの実現時期が不確実な場合に有効です。

同種写像ベースのゼロ知識証明は、新たな研究分野です。両方の曲線が与えられたときに同種写像の経路phi: E -> E'を見つける同種写像経路問題は、知識証明方式の困難な問題として利用できます。「EからE'への同種写像を知っている」ことを証明するSigmaプロトコルにより、同種写像そのものを明らかにせずに認証できます。Vero（2022年）は、実用的な同種写像ベースのZK証明システムを実証しました。これらのZK証明は、命題が2つのj-不変量だけで表されるため、自然にコンパクトです。しかし現在は、実用化には遅すぎます。同種写像の計算が改善されれば、仮定の多様性が重視される用途において、同種写像ベースのZK証明は格子ベースまたはハッシュベースの証明に代わる手段となる可能性があります。

同種写像技法は耐量子暗号に関係するだけでなく、古典的な楕円曲線暗号にも応用されています。楕円曲線の点を数えるSchoof-Elkies-Atkin（SEA）アルゴリズムは、同種写像を使用してフロベニウスのトレースを計算し、安全な楕円曲線パラメーターを効率的に生成できるようにします。同種写像は、ECDLPの計算におけるPollardのrho法の改良にも登場します。指定された位数を持つ曲線を構成するCM（Complex Multiplication）法では、根本的に同種写像に関係する類多項式を使用します。同種写像ベースの暗号解析ツール（滑らかな次数の同種写像経路を見つけるもの）は、隠れたトラップドアがないか提案された楕円曲線パラメーターを評価するために使用されます。これは、Dual EC DRBGに関する懸念にも直接関係します。

2024年時点で、NISTやその他の主要機関によって標準化された同種写像ベース方式はありません。NISTのPQCプロセスでは、ML-KEM、ML-DSA、SLH-DSA、FN-DSAが標準化されていますが、いずれも格子ベースまたはハッシュベースです。NISTはPQC署名の第2ラウンド評価を実施しており、SQISignも応募していますが、性能面で懸念があります。同種写像コミュニティは、実用的な署名生成時間（1秒未満を目標）を実現する、より成熟したSQISign 3.0の開発に取り組んでいます。ISOとETSIはいずれも、同種写像方式を標準化していません。近い将来に最も可能性が高い標準化の道筋は、署名サイズの最小化が必要なニッチな用途向けにSQISignを標準化することです。ただし、必須プリミティブではなく情報提供目的の標準となる可能性があります。広範な導入には、桁違いの性能向上が必要です。

2024年時点における同種写像ベース暗号の活発な研究方向は、次のとおりです。(1) SQISign 2.0、HD、Fast SQISignなどの派生方式によって署名性能を改善し、1秒未満の処理を目指す研究。(2) CSIDHとその派生方式の量子安全性分析。Kuperberg攻撃の推定を精緻化し、この攻撃に耐える代数構造を探る研究。(3) 新たな困難性の仮定。超特異自己準同型環の計算や、虚二次環上の加群問題など。(4) 同種写像ベースのOblivious PRFと、プライバシー保護プロトコルへの応用。(5) 同種写像演算のハードウェア実装。FPGAの並列性を活用してCSIDHの類群作用を実装する研究。(6) 同種写像ベースの群作用を汎用群作用暗号のフレームワークと統合し、新たな関数暗号や属性ベース方式につなげる研究。

SIKEが破られたことで、同種写像暗号を完全に諦めるべきだと思うかもしれません。しかし、暗号研究コミュニティは反対の見方をしています。今回の解読が貴重だったのは、どの構造が安全でないのか（SIDHにおける捩れ点の漏えい）と、どの構造が依然として困難なのか（自己準同型環や類群作用）を明らかにしたからです。同種写像の研究が重要であり続ける理由は、次のとおりです。(1) 耐量子暗号の多様性 — LWEが破られた場合に備え、格子以外の安全性仮定を持つことで、システム全体のリスクを減らせます。(2) SQISignは、現在競合する方式がないほどコンパクトな、独自性の高い署名を提供します。(3) 同種写像の技術は、楕円曲線暗号の解読やパラメーター検証に役立ちます。(4) 数学的に美しく、発展性があります。SIKEを破るために開発されたツールは、他の分野で使われる楕円曲線の自己準同型環への理解を直接深めました。

SQISign署名の基盤となる困難性仮定は何ですか？

2022年にSIKEが破られた後も、同種写像暗号は異なる困難性仮定を通じて発展を続けています。SQISignは、自己準同型環の困難性に基づき、177バイトという現在知られている最小サイズの耐量子署名を提供します。性能も向上しており、1秒未満が目標です。FESTAは、KEM向けにSIDHの捩れ点の漏えいを回避する設計を採用しています。SCALLOPは、向き付けられた曲線を使って量子計算機に対する128ビット安全性を目指します。ハイブリッドな同種写像・格子方式は、安全性仮定の多様性を提供します。現在、標準化された同種写像方式はありません。近い将来に最も標準化される可能性が高いのはSQISignです。SIKEが破られたことで、同種写像プロトコルで何を隠す必要があるのかについての理解が深まり、楕円曲線暗号全体で使われる新しい数学的ツールも生まれました。