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）に委譲されるため、量子ビットの節約は計数レジスタの排除によってのみもたらされます。

• エンコーディング: 基盤となる戦略と同じ（群インデックス）
• 量子ビット数: 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倍に対して）

比較

QFT算術プリミティブ

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

結果

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

すべての実行はIBM Quantumオープンインスタンスプランで実行されました。このプランでは月額10分の無料量子計算が許可されています。完全な実行ログはexecutions/フォルダにあります。

リップルキャリー戦略（戦略6）により、大幅な飛躍が可能になりました。10ビット（40量子ビット、200万ゲート）から**17ビット（69量子ビット、112Kゲート）**へと、7ビットの鍵サイズ増加に対して2量子ビットゲート数が18分の1に削減されました。CDKM加算器の最近接ゲート構造はIBMのheavy-hexトポロジに効率的にマッピングされ、ルーティングオーバーヘッドを約1倍に保ちます。

Semiclassical PE: IBMハードウェア上のダイナミックサーキット

半古典戦略（--oracle google）は、IBM Heron r2プロセッサ上でダイナミックサーキット（中間回路reset、if_testによる古典的条件付きpゲート）を使用して、4ビット、6ビット、7ビットでの鍵復元に成功しました。7ビットでは、回路はわずか14量子ビット（標準の置換アプローチでは26量子ビット）を使用し、トランスパイル後も同等の2Qゲート数を生成します。

8ビット以上では、現在のIBMハードウェア上で半古典アプローチは実用的ではなくなります。if_elseとresetはHeron r2でサポートされていますが（バックエンドターゲット検査で確認）、各古典フィードバックポイントは完全なQPU同期を必要とします。つまり、古典コントローラが約16個のアクティブ量子ビットの条件を処理している間、156個すべての物理量子ビットがアイドル状態になる必要があります。約295KのCZゲートが16以上のフィードバックポイントに分割されているため、1ショットあたりの実行オーバーヘッドにより、ジョブがQPUの時間予算を超えます。ダイナミックサーキットなしで同じゲート数を単一の連続バッチとして実行する標準の置換アプローチは、この規模で正常に完了します。

近似QFTトランケーション（max_correctionsパラメータ）は、if_elseブロックの数をO(n^2)からO(n)に削減します。これは、測定ステップごとに最も近いk個の位相補正のみを保持し（kを超える角度はpi/2^{k+1}未満に寄与し、ハードウェアノイズフロアを下回る）ます。max_corrections=1の場合、8ビット回路には16個のif_elseブロックがありますが、それでもこのゲート数ではIBMハードウェア上でタイムアウトを引き起こすのに十分です。

ノイズとフィデリティ分析

推定回路フィデリティ

典型的なIBM Quantum 2量子ビット（CX）ゲートフィデリティを約99.5%と仮定すると、推定回路フィデリティはゲート数に応じて指数関数的に低下します。

回路フィデリティはF ≈ (0.995)^{CX_count}として計算されます。4ビットを超えると、推定フィデリティは天文学的に小さくなります。出力分布は圧倒的にノイズです。

それでも機能する理由

8ビット以上では、各ショットはほぼ一意のビットストリングを生成します（8ビットで8,192ショット中8,128の一意の結果、16ビットと17ビットでは20,000すべてが一意）。出力はビットストリングレベルで一様ランダムサンプリングと区別できません。それでもアルゴリズムは正しい秘密鍵を復元します。

重要な洞察は、Shorの後処理は生のビットストリング分析が示す以上にノイズに対してロバストであるということです。各ショットは(j, k, r)測定トリプルを生成します。抽出ではd_cand = (r - j) · k^{-1} mod nを計算し、d_cand · G == Qで検証します。真のdのみがEC検証に合格するため、数千のノイズショットの中から1つの正しい候補があれば十分です。

純粋にランダムな(j, k, r)トリプルは、確率約1/nで正しいd_candを生成します。Sショットの場合、ノイズのみから予想される検証済みヒット数は約S/nです。17ビット（n=65,173、S=20,000）では、ノイズヒットの期待値は約0.3です。この規模で復元が成功した場合、古典的なノイズフロアを超える量子信号の証拠を提供します。

ショット数>> nの小さな曲線（例：n=547、1,024ショットの10ビット）では、ノイズフロアは候補あたり約1,024/547 ≈ 1.9票です。少数の信号を含むショットでも、正しいdをノイズフロアより上に押し上げます。これにより、計算を不可能にすると思われる回路フィデリティにもかかわらず、アルゴリズムが成功する理由が説明されます。

量子信号と古典ノイズ

おもちゃ規模では、抽出の検証ステップ（d_cand * G == Q）は真のdのみを受け入れるフィルターとして機能します。これは、純粋にランダムな(j, k, r)トリプルでも、実行あたり約shots / nの割合で有効な候補を生成することを意味します。shots >> nの場合、ランダムノイズだけでも高い確率でdを復元できます。

量子回路がこの古典的なノイズフロアを超えて信号に寄与しているかどうかをテストするために、6ビットチャレンジ（n=31）をわずか8ショット（群位数を大幅に下回る）で10回、ibm_kingstonで実行しました。

結果: 4/10成功（40%）。古典的なノイズベースラインは約20%（モンテカルロシミュレーションで計算：8個のランダムビットストリングから(r-j)*k_inv mod 31を検証でフィルタリング）です。片側二項検定: P(X >= 4 | n=10, p=0.20) = 0.121。ノイズフロアに対する2倍の改善を示しています。個別にはp < 0.05で統計的に有意ではありません（それには5以上の成功が必要）、観測された割合は、実行あたりランダムチャンスが提供するものを超えて、量子信号が約1〜2個の追加の有効な(j, k)ペアに寄与していることと一致しています。

この結果は、古典的なノイズフロアと理論的な量子優位性のレジームの間に位置しています。n >> shotsとなるより大きな曲線サイズでは、ノイズベースラインが1%未満に低下し、鍵復元が成功すれば量子計算の強力な証拠となります。

クイックスタート```bash

git clone https://github.com/GiancarloLelli/quantum.git cd quantum

python -m venv . Scripts\Activate.ps1 # For Windows only

pip install -r requirements.txt

### 実行方法

[IBM Quantum](https://quantum.ibm.com/) アカウントが必要です。初回実行時に API トークンを渡すと、ローカルに保存されます:```bash
# Solve the 4-bit challenge curve:
python projecteleven.py --challenge 4 --token YOUR_IBM_TOKEN --backend ibm_marrakesh

# Subsequent runs (token already saved):
python projecteleven.py --challenge 4 --backend ibm_marrakesh

# Use the coordinate-based quantum oracle:
python projecteleven.py --challenge 4 --oracle coordinate --backend ibm_marrakesh

# Use the arithmetic oracle (coordinate encoding + QFT primitives):
python projecteleven.py --challenge 4 --oracle arithmetic --backend ibm_marrakesh

# Use ripple-carry modular addition (CDKM — best for 8-bit+):
python projecteleven.py --challenge 16 --oracle ripple --backend ibm_fez --shots 20000

# Use Google semiclassical phase estimation (qubit-recycled):
python projecteleven.py --challenge 4 --oracle google --backend ibm_marrakesh

# Use a specific IBM Quantum instance:
python projecteleven.py --challenge 4 --instance ibm-q/open/main --backend ibm_marrakesh

# Verify curve parameters without quantum execution:
python projecteleven.py --curve curve_4 --verify-only

CLIオプション

プロジェクト構造```

projecteleven.py # Shor solver — dense unitary approach + CLI entry point quantum_arithmetic.py # Efficient permutation decomposition + QFT arithmetic primitives quantum_oracle.py # Coordinate-based oracle + arithmetic oracle framework google_semiclassical.py # Google semiclassical PE — qubit-recycled phase estimation ripple_carry_shor.py # Ripple-carry modular addition oracle (CDKM) — best for 8-bit+ input_curves.json # Challenge curves (4-bit to 30-bit) problem/curves.py # Curve generation utility requirements.txt # qiskit, qiskit-ibm-runtime

## 参考文献

- P. Shor, ["量子計算のためのアルゴリズム：離散対数と素因数分解"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard, ["2n+3量子ビットを用いたShorのアルゴリズムの回路"](https://arxiv.org/abs/quant-ph/0205095) (2003)
- S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton, ["新しい量子リップルキャリー加算回路"](https://arxiv.org/abs/quant-ph/0410184) (2004)
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter, ["楕円曲線離散対数を計算するための量子リソース見積もり"](https://arxiv.org/abs/1706.06752) (2017)
- R. Griffiths, C.-S. Niu, ["量子計算のための半古典的フーリエ変換"](https://arxiv.org/abs/quant-ph/9511007) (1996)
- R. Babbush 他, ["量子脆弱性に対する楕円曲線暗号通貨の保護：リソース見積もりと緩和策"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## ライセンス

このプロジェクトは、Q-Day Prize Challengeへの応募作品であり、[MIT LICENSE](https://github.com/yuvadm/quantumslop/blob/HEAD/LICENSE)の下で公開されています。