Clémence Chevignard、Pierre-Alain Fouque、André Schrottenloherによる技術論文は、EUROCRYPT 2026で発表予定であり、1,098個の論理量子ビットを使用して256ビット楕円曲線上の離散対数問題（ECDLP）を解く手法を説明している。これは、同じセキュリティレベルに対する従来の推定値2,124個の論理量子ビットからの削減である。このアプローチは、nビット曲線に対して3.12nの空間計算量を達成する、空間最適化されたショアのアルゴリズムの実装を利用している。これにより、256ビットECCを破るために必要な量子ビット数は、現在推定2,043個の論理量子ビットを必要とする3072ビットRSAの因数分解を下回ることになる。
量子ビット数の削減は、ルジャンドル記号に基づく単一ビットハッシュ関数を使用した出力圧縮によって達成される。一意なアフィン座標を得るために剰余逆元を明示的に計算する代わりに（このプロセスは通常、かなりの補助量子ビット空間を必要とする）、アルゴリズムは射影座標のルジャンドル記号を計算する。これは、大きな整数演算を二分木内で処理されるより小さな剰余に分解する剰余数系（RNS）によってサポートされている。このアーキテクチャは、標準的な座標変換をより空間効率の高い演算パイプラインに置き換えるが、計算負荷をメモリから論理演算にシフトさせる。
この手法は論理量子ビットの閾値を下げるが、ゲート数の増加をもたらす。漸近的計算量は3次スケーリングから4次スケーリングに増加する。256ビット曲線の場合、実装は1回の実行あたり約238.10個のトフォリゲートを必要とし、これは以前の推定値である約230からの大幅な増加である。低い補助空間を維持するため、チームは測定ベースの逆計算を使用して二分木の走査中に量子ビットを再利用する「spooky pebbling」戦略を採用した。研究者らは、論理量子ビットが主要なボトルネックである初期の耐故障性システムにとって、このトレードオフはより小規模なハードウェア構成で暗号解析アルゴリズムを実行するための実行可能な道を提供すると結論づけた。
RNSベースの点乗算とルジャンドル記号圧縮に関する完全な技術的詳細については、IACR ePrintアーカイブの論文を参照されたい。また、Unitary FoundationのWilliam Zengによるこれらの結果に関する解説も閲覧可能である。
2026年3月26日
