ECDLPのためのShorのアルゴリズム — Q-Day Prize Submission

楕円曲線離散対数問題（ECDLP）のための量子ソルバーで、Project ElevenによってQ-Day Prize Challenge向けに構築されました。目標は、Shorのアルゴリズムを使用して実際の量子ハードウェア上でECC秘密鍵を復元することです。

• 著者: Giancarlo Lelli
• 連絡先: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• 背景: エンタープライズソフトウェア、フルスタックアーキテクチャ、クラウドネイティブ開発において10年以上の経験を持つテクノロジーリーダー。コンピュータサイエンスのバックグラウンドを持ち、.NET、Python、Rust、Cloudエコシステムにわたる実践的な経験があります。現在は、ソリューションアーキテクチャとセールスエンジニアリングに焦点を当てたCloud GTMスペシャリストとして活動しています。

アプローチ

すべてのチャレンジ曲線は、secp256k1ファミリーに一致するF_p上のy^2 = x^3 + 7（a = 0, b = 7）を使用しています。このソルバーは、ECDLPに対するShorのアルゴリズムの2レジスタ変種を実装しています。

1. 計数レジスタ|j>, |k>を一様な重ね合わせに準備する（Hadamard）
2. 2t個の制御付き点加算（t = num_counting qubits）を介して|j>|k>|jG + kQ>を計算
3. 点レジスタを測定し、ある群要素Rに崩壊させる
4. 計数レジスタに逆QFTを適用
5. j, kを測定し、関係式j + kd = r (mod n)からdを抽出

秘密鍵dは、群位数nを法として同じ線形関係を満たす複数の(j, k)サンプルを収集することで復元されます。このソルバーは、制御付き点加算のための6つのオラクル戦略をサポートしており、曲線のサイズに基づいて自動的に選択されるか、--oracleで手動で指定できます。

オラクル戦略

戦略1: Dense Unitary（デフォルト、n_bits <= 6）

最大約6ビットの群位数を持つ曲線に使用されます。projecteleven.pyで実装されています。

各制御付き点加算「add S」は、qc.unitary()を介して適用される2^(n+1) x 2^(n+1)の置換行列として表現されます。この行列は完全な群作用をエンコードします。左上ブロックは単位行列（制御=0）、右下ブロックは写像P -> P+S（制御=1）に従って基底状態を置換します。

• エンコーディング: 群インデックス（0..n-1）
• メモリ: 行列ごとにO(2^{2n})
• 量子ビット数: 2t + n（2つの計数レジスタ + 点レジスタ）
• 制限: Qiskitのユニタリ分解はO(4^n)であるため、約6ビットを超えると実行不可能

戦略2: Efficient Permutation Decomposition（デフォルト、n_bits > 6）

より大きな曲線に使用されます。quantum_arithmetic.pyで実装されています。

密行列を構築する代わりに、各「add S」の置換はトランスポジション（互換）にサイクル分解されます。各トランスポジション（2つの基底状態|a> <-> |b>の交換）は次のように実装されます。

1. CNOT削減 -- ピボットビットから他のすべての異なるビットへのCNOTにより、マルチビットの差をシングルビットの差に減らす
2. マルチ制御X -- 他のすべてのビットがターゲットパターンに一致することを条件とする、ピボットビット上のMCXゲート
3. CNOTの取り消し -- ステップ1を逆にして、非ピボットビットを復元

MCXは**(n-2)個の専用アンシラ量子ビットを用いたVチェーン分解を使用し、アンシラなしのO(n^2)ではなく、MCXごとにO(n)個のToffoliゲートを実現します。各制御付き加算は独立したサブ回路**として構築され、単一の不透明ゲートとして追加されるため、QiskitでのDAGの二次的な増大を回避します。

• エンコーディング: 群インデックス（0..n-1）
• メモリ: 加算ごとにO(N)（N = 群位数）
• 量子ビット数: 2t + n + (n-2)個のアンシラ
• 加算あたりのゲート数: O(N * n)

戦略3: Coordinate-Based Quantum Oracle（--oracle coordinate）

約6ビットまでの曲線で利用可能です。quantum_oracle.pyで実装されています。

点を群インデックスとしてエンコードする代わりに、量子レジスタはバイナリの実際の**(x, y)体要素座標**とアイデンティティフラグを保持します。点レジスタのレイアウトは次のとおりです。

• x_reg: f_bits量子ビット（f_bits = ceil(log2(p))）
• y_reg: f_bits量子ビット
• id_flag: 1量子ビット（1 = 無限遠点）

各制御付き「add S」は、すべての有効な座標エンコーディングにわたるEC加算式から計算され、座標レジスタ上の置換を生成します。この置換は、戦略2と同じCNOT削減+MCXインフラストラクチャを使用してトランスポジションにサイクル分解されます。

• エンコーディング: (x, y, id_flag)座標
• 量子ビット数: 2t + 2f_bits + 1 + max(0, 2f_bits - 1)個のアンシラ
• 加算あたりのゲート数: O(N * f_bits)

戦略4: Arithmetic Oracle（--oracle arithmetic）

多項式スケーリングの点加算のためのフレームワーク。quantum_oracle.pyとquantum_arithmetic.pyで実装されています。

戦略3と同じ座標エンコーディングを使用し、QFTベースのモジュラー算術プリミティブを構成要素として、完全に算術的な点加算を目指します。コードベースには、テスト済みの次の実装が含まれています。

• Beauregardモジュラー加算器 -- QFTベース（(target + constant) mod p）、適切なアンシラのアンコンピュート付き
• 量子-量子モジュラー乗算 -- |a>|b>|0> -> |a>|b>|a*b mod p>、シフトアンド加算と明示的なモジュラー2倍化を使用、O(n^3)ゲート
• モジュラー逆元置換 -- |x> -> |x^{-1} mod p>、ルックアップテーブルのトランスポジションによる
• 制御付き量子-量子モジュラー加算 -- 制御付き|a> -> |a + b mod p>、Beauregard削減を使用

算術プリミティブは、点加算あたりO(n^3)のスケーリングを達成します（置換アプローチのO(N*n)に対して）。ただし、QFTベースの操作は約150倍の定数係数を持つため、算術アプローチは約20ビット以上の群位数を持つ曲線でのみ効率的です。現在のチャレンジサイズ（最大12ビット）では、置換ベースの加算器の方が高速であり、デフォルトで使用されます。

戦略5: Google Semiclassical Phase Estimation（--oracle google）

google_semiclassical.pyで実装されています。Griffiths & Niu（1996）の量子ビットリサイクル位相推定技法に触発され、Babbush et al.（2026）でsecp256k1 ECDLPリソース推定のために大規模に適用されました。Babbush et al.の論文は2026年3月30日に公開されました。

2つのマルチ量子ビット計数レジスタ（j, k）と一括逆QFTを、2つの単一リサイクル量子ビットと古典的条件付き位相補正に置き換えます。各計数レジスタビットは順次処理されます。|+>に準備し、制御付き点加算を適用し、以前に測定されたすべてのビットに基づいて位相を補正し、その後測定します。Qiskitのダイナミックサーキットプリミティブresetとif_testにより、IBM Quantumハードウェア上でこれが可能になります。

制御付き点加算のオラクルは既存のインフラストラクチャ（<=6ビットの場合はdense unitary、>6ビットの場合はefficient permutation）に委譲されるため、量子ビットの節約は計数レジスタの排除によってのみもたらされます。

曲線サイズ	標準量子ビット数	半古典量子ビット数	節約率	ハードウェア検証
4ビット (n=7)	11	5	55%	あり
6ビット (n=31)	17	7	59%	あり
7ビット (n=79)	26 + アンシラ	14	46%	あり
8ビット (n=139)	25 + アンシラ	10 + アンシラ	60%	なし（QPU同期オーバーヘッド）
10ビット (n=547)	31 + アンシラ	12 + アンシラ	61%	なし（QPU同期オーバーヘッド）

• エンコーディング: 基盤となる戦略と同じ（群インデックス）
• 量子ビット数: 2 + n_bits + アンシラ（標準: 2t + n_bits + アンシラ）
• トレードオフ: ダイナミックサーキット（中間回路測定、リセット、古典的条件付きゲート）が必要。IBM Heron r2では7ビットまで動作可能。8ビット以上では、古典的フィードバックの同期オーバーヘッドがQPUの時間予算を超える

戦略6: Ripple-Carry Modular Addition（--oracle ripple）

ripple_carry_shor.pyで実装されています。制御付き点加算にCDKMリップルキャリー加算器（Cuccaro et al. 2004）を使用し、密なユニタリ行列とサイクル分解されたトランスポジション回路の両方を置き換えます。

群インデックスエンコーディングでは、点P = kGは巡回群内のそのインデックスkで表されます。S = sGを加算することは、**既知の定数sのモジュラー加算（mod n）**になります。重要な洞察: 各制御付き点加算は、QiskitのCDKMRippleCarryAdderとIntegerComparatorを介して実装された、既知の定数の単一の制御付きモジュラー加算に帰着します。

オラクルは2m個の制御付きモジュラー加算（計数レジスタごとにm個）で構成され、各制御付きmod-addは次の処理を実行します。

1. 定数のロード: 制御量子ビットからのCXを介してアンシラレジスタにロード
2. CDKM半加算器: アンシラをアキュムレータに加算（最近接ゲートのみ）
3. 整数比較器: オーバーフローを検出（acc >= n）
4. 条件付きnの減算: フラグ制御による2^m1 - nの加算
5. フラグのアンコンピュート: キャリーベースのプロービングによる

回路構築に秘密鍵dの知識は使用されません。Gの冪乗の群インデックスは2^i mod n（公開）として計算されます。Qの冪乗の群インデックスは、Gによって生成された巡回群の公開された列挙から導出されます。点Qはこの列挙内で検索されます。

• エンコーディング: 群インデックス（0..n-1）
• 量子ビット数: 4m + 5、ここでm = ceil(log2(n))
• 加算あたりのゲート数: O(m)のCDKM操作、それぞれO(m)のCXゲート
• 総CXスケーリング: O(m^3)
• ハードウェアマッピング: CDKMは最近接ゲートのみを使用するため、IBM heavy-hexトポロジ上でのルーティングオーバーヘッドは約1倍（QFTベースの加算器の26〜33倍に対して）

曲線サイズ	量子ビット数	2Qゲート数（トランスパイル後）	ハードウェア検証
4ビット (n=7)	17	1,824	あり（シミュレーション）
8ビット (n=139)	37	11,224	—
10ビット (n=547)	45	17,204	—
12ビット (n=2143)	53	24,304	—
16ビット (n=32497)	65	98,049	あり
17ビット (n=65173)	69	111,816	あり

比較

指標	Dense Unitary	Efficient Permutation	Coordinate Oracle	Arithmetic Oracle	Semiclassical PE	Ripple-Carry
点のエンコーディング	群インデックス	群インデックス	(x, y, id_flag)	(x, y, id_flag)	群インデックス	群インデックス
加算あたりのスケーリング	O(4^n) 分解	O(N * n)	O(N * f_bits)	O(n^3) 漸近的	O(N * n)	O(m^2)
量子ビット数（4ビット）	11	13	24	24	5	17
量子ビット数（6ビット）	17	21	36	36	9	25
2Qゲート数（4ビット）	774	~1,200	6,449	6,449	~1,200	1,824
2Qゲート数（6ビット）	23,471	~38,000	95,254	95,254	~38,000	4,582
実用的範囲	<= 6ビット	<= ~16ビット	<= 6ビット	>= 20ビット（将来）	<= ~16ビット	<= ~20ビット

QFT算術プリミティブ

コードベースには、256ビットでの完全に算術的な座標エンコーディングへの基盤として、QFTベースのモジュラー算術構成要素（Beauregard/Draper加算器、量子-量子モジュラー乗算、モジュラー逆元/否定）が含まれています。これらのプリミティブは、p=13までの素数に対してStatevectorシミュレーションで正しく動作することが確認されています。

結果

IBM Quantumハードウェア上で、17ビットまでのチャレンジ曲線に対して秘密鍵の復元に成功しました。