量子攻撃に必要な量子ビットとゲート数を同時削減、楕円曲線暗号の新アルゴリズム

楕円曲線暗号を利用する組織にとって、耐量子計算機暗号（PQC）への移行計画を過去の資源見積もりだけで判断することは難しくなっている。ジョージア工科大学とQED Auditに所属するSunghyeon Jo、Gye Jin Leeが9月14日に公開したプレプリントは、楕円曲線離散対数問題を解く量子アルゴリズムについて、必要な論理量子ビット数とToffoliゲート数を理論上同時に削減した。暗号解読を実行できる規模の耐障害量子コンピュータはまだ実現していないが、組織には暗号資産の棚卸しと、長期間の秘匿性を必要とするデータの優先順位付けが求められる。

■論理量子ビット数とゲート複雑性を同時に改善

IACR Cryptology ePrint Archiveに掲載されたプレプリントは、nビットの素体上に定義された楕円曲線離散対数問題（ECDLP）を、5n/2＋o(n)論理量子ビットと、ほぼ2次のÕ(n²) Toffoliゲートで解く量子アルゴリズムを提示した。これは具体的な量子コンピュータ上で暗号を解読した結果ではなく、将来の耐障害量子計算に必要となる回路資源の漸近的な評価である。

2026年7月に公開されたHan Luoらの先行研究は、3n＋6⌊log₂n⌋＋O(1)論理量子ビットと、O(n³/log n)のToffoliゲートを必要とするアルゴリズムを示していた。JoとLeeは、量子ビット数の支配項を3nから5n/2へ下げるとともに、ゲート複雑性をほぼ2次へ改善した。量子ビット数の支配項では約17％の削減に当たる。

楕円曲線暗号は、HTTPSなどで使われる鍵共有、ソフトウェアのコード署名、暗号資産の取引署名、企業システムの認証などに利用されている。代表的な方式には、共有鍵を確立するECDH（楕円曲線Diffie-Hellman鍵共有）と、デジタル署名方式のECDSAがある。

これらの安全性を支える数学的問題の一つがECDLPである。楕円曲線上の生成元Gと公開点Qが与えられたとき、Q＝kGを満たす整数kを求める問題で、実用的な鍵長では既知の古典アルゴリズムによって効率的に解くことが難しい。一方、十分な規模と精度を備えた耐障害量子コンピュータでShorのアルゴリズムを実行できれば、原理上は多項式時間で解ける。

研究では、NIST P-256やsecp256k1などの256ビット素体曲線が主要な評価対象となっている。secp256k1はBitcoinやEthereumの取引署名に使われており、量子計算によるECDLP攻撃の資源要件を考える際の重要な事例である。

■モジュラー逆元計算の省資源化

JoとLeeの研究の中核は、3n/2＋o(n)論理量子ビットと、ほぼ線形のÕ(n) Toffoliゲートで動作する、厳密なインプレース型モジュラー逆元計算回路である。モジュラー逆元計算とは、有限体上である数の乗法逆元を求める処理を指す。

ShorのアルゴリズムでECDLPを解く量子回路では、楕円曲線上の点加算を繰り返し実行する。アフィン座標による点加算ではモジュラー逆元計算が必要になり、中間値を保存するレジスタも含めて、回路の量子ビット数と演算量を左右する主要な処理となる。

新しい回路は、2進ユークリッド互除法で成立する不変量を利用する。連続する剰余R、rと、それらに対応する係数の絶対値T、tについて、Rt＋rT＝pという関係を保つことで、4つの値すべてを常時保存する必要をなくした。R、r、T、tのうち3つだけを継続的にレジスタへ保持し、残る値は必要になった時点で再構成する。

一時的に使う補助量子ビットについては、測定を利用したアンコンピュテーションを採用した。不要になった中間情報を回路全体の逆実行によって消去するのではなく、更新後の状態から一時データを復元して消去することで、作業領域を抑えている。

さらに、古典的な代数恒等式であるHuaの恒等式を使い、アフィン座標の点加算で必要となる可変値の二乗を含む乗算を、逆元計算を使った処理に変換した。省資源化した逆元計算回路と組み合わせることで、制御付き点加算を5n/2＋o(n)論理量子ビット、Õ(n) Toffoliゲートで実行できるとしている。

ECDLP全体では点加算が繰り返されるため、最終的なゲート複雑性はÕ(n²)となる。今回の論文では、量子ビット数とゲート数が別々の最適化によって改善されたのではなく、逆元計算を省資源化した一つの設計が両方の削減につながっている。

■Toffoliゲート数も実行コストを左右

量子攻撃の資源見積もりでは、必要な論理量子ビット数が注目されやすい。しかし、耐障害量子コンピュータ上で実行する際には、回路が必要とするToffoliゲート数も重要になる。

Toffoliゲートは、可逆な量子算術回路で広く使われる非Clifford演算の一つである。代表的な耐障害量子計算方式では、こうした演算を高い信頼性で実行するために、マジック状態の準備や蒸留などの追加処理が必要になる。このため、Toffoliゲート数は計算時間、マジック状態の供給能力、誤り訂正に必要な資源を見積もるうえで重要な指標となる。

少ない量子ビットで動く回路であっても、ゲート数が大きく増えれば、計算時間や付随するハードウェア要件が増大する可能性がある。反対に、ゲート数を抑えられれば、同じ量子ビット数でも実行時間や誤り訂正上の負担を軽減できる可能性がある。量子ビット数だけで攻撃の実行可能性を評価するのではなく、回路の幅と演算量を併せて見る必要がある。

Clémence Chevignard、Pierre-Alain Fouque、André SchrottenloherによるEUROCRYPT 2026の研究は、256ビット素体曲線について1,193論理量子ビットという具体的な見積もりを示した。一方で、22回の独立した実行を必要とし、各実行には2^38.10 Toffoliゲートを要すると見積もっている。量子ビット数を減らす代わりに、ゲート数が増える設計である。

Luoらの研究は、256ビット素体曲線に対する具体的な評価として835論理量子ビットを報告した。ただし、この数値には3nという支配項だけでなく、対数項や定数項も含まれる。JoとLeeの新しい式でn＝256を代入すると支配項は640となるが、論文はP-256やsecp256k1について下位項を含む具体的な論理量子ビット数を示していない。したがって、640量子ビットをそのまま具体的な攻撃回路の総量子ビット数として比較することはできない。

■2026年に相次いだ資源見積もりの更新

楕円曲線暗号に対する量子攻撃の資源見積もりは、2026年に相次いで更新された。2017年にMartin Roettelerらが公表した研究は、nビット素体上のECDLPを最大9n＋2⌈log₂n⌉＋10量子ビットで解く回路を提示した。n＝256では約2,330量子ビットとなり、長年にわたって代表的な比較基準の一つ

元記事: Elliptic Curve Encryption’s Quantum Attack Cost Falls on Two Fronts in Georgia Tech Paper