ECDLP를 위한 쇼어 알고리즘 — Q-Day Prize 제출물

타원곡선 이산로그 문제(ECDLP)를 위한 양자 솔버로, Project Eleven이 Q-Day Prize Challenge를 위해 제작했습니다. 목표: 쇼어 알고리즘을 사용하여 실제 양자 하드웨어에서 ECC 개인키를 복구합니다.

• 저자: Giancarlo Lelli
• 연락처: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• 배경: 엔터프라이즈 소프트웨어, 풀스택 아키텍처, 클라우드 네이티브 개발 분야에서 10년 이상 경력을 가진 기술 리더입니다. 컴퓨터 과학 배경을 바탕으로 .NET, Python, Rust, 클라우드 생태계 전반에 걸친 실무 경험이 있습니다. 현재 솔루션 아키텍처와 영업 엔지니어링에 중점을 둔 Cloud GTM Specialist로 활동하고 있습니다.

접근 방식

모든 챌린지 곡선은 F_p 상에서 y^2 = x^3 + 7을 사용하며 (a = 0, b = 7), secp256k1 계열과 일치합니다. 솔버는 ECDLP를 위한 쇼어 알고리즘의 2-레지스터 변형을 구현합니다:

1. 계수 레지스터 |j>, |k>를 균일 중첩 상태로 준비 (Hadamard)
2. 2t개의 제어된 점 덧셈을 통해 |j>|k>|jG + kQ> 계산 (t = num_counting qubits)
3. 점 레지스터를 측정하여 일부 군 원소 R로 붕괴
4. 계수 레지스터에 역 QFT 적용
5. j, k를 측정하고 관계식 j + kd = r (mod n)에서 d 추출

개인키 d는 군 위수 n에 대해 동일한 선형 관계를 만족하는 여러 (j, k) 샘플을 수집하여 복구됩니다. 솔버는 곡선 크기에 따라 자동으로 선택되거나 --oracle을 통해 수동으로 선택되는 6가지 오라클 전략을 제어된 점 덧셈에 대해 지원합니다.

오라클 전략

전략 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 (두 계수 레지스터 + 점 레지스터)
• 제한사항: Qiskit의 유니터리 분해는 O(4^n)이므로 ~6비트를 넘으면 실행 불가능

전략 2: Efficient Permutation Decomposition (n_bits > 6의 기본값)

더 큰 곡선에 사용됩니다. quantum_arithmetic.py에 구현되어 있습니다.

밀집 행렬을 구축하는 대신, 각 "add S" 순열은 전치로 순환 분해됩니다. 각 전치(두 기저 상태 |a> <-> |b>의 교환)는 다음으로 구현됩니다:

1. CNOT 감소 -- 피벗 비트에서 다른 모든 비트로 CNOT을 적용하여 다중 비트 차이를 단일 비트 차이로 축소
2. 다중 제어 X -- 다른 모든 비트가 대상 패턴과 일치할 때 피벗 비트에 MCX 게이트 적용
3. CNOT 취소 -- 1단계를 되돌려 비-피벗 비트 복원

MCX는 (n-2)개의 전용 보조 큐비트를 사용하는 **V-체인 분해(V-chain decomposition)**를 사용하여, 보조 큐비트가 없을 때의 O(n^2) 대신 MCX당 O(n)개의 토폴리 게이트를 제공합니다. 각 제어된 덧셈은 고립된 서브회로로 구축되어 단일 불투명 게이트로 추가되며, Qiskit에서 이차 DAG 증가를 방지합니다.

• 인코딩: 군 인덱스 (0..n-1)
• 메모리: 덧셈당 O(N) (N = 군 위수)
• 큐비트: 2t + n + (n-2) ancillas
• 덧셈당 게이트: O(N * n)

전략 3: Coordinate-Based Quantum Oracle (--oracle coordinate)

최대 ~6비트 곡선에 사용 가능합니다. quantum_oracle.py에 구현되어 있습니다.

점을 군 인덱스로 인코딩하는 대신, 양자 레지스터는 실제 (x, y) 체 원소 좌표를 이진수로 보유하고 항등 플래그를 추가합니다. 점 레지스터 레이아웃은 다음과 같습니다:

• x_reg: f_bits qubits (f_bits = ceil(log2(p)))
• y_reg: f_bits qubits
• id_flag: 1 qubit (1 = point at infinity)

각 제어된 "add S"는 모든 유효한 좌표 인코딩에 대해 EC 덧셈 공식으로 계산되어, 좌표 레지스터에 대한 순열을 생성합니다. 이 순열은 전략 2와 동일한 CNOT 감소 + MCX 인프라를 사용하여 전치로 순환 분해됩니다.

• 인코딩: (x, y, id_flag) 좌표
• 큐비트: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) ancillas
• 덧셈당 게이트: O(N * f_bits)

전략 4: Arithmetic Oracle (--oracle arithmetic)

다항식 스케일링 점 덧셈을 위한 프레임워크. quantum_oracle.py와 quantum_arithmetic.py에 구현되어 있습니다.

전략 3과 동일한 좌표 인코딩을 사용하며, QFT 기반 모듈러 산술 프리미티브를 완전 산술 점 덧셈을 위한 구성 요소로 사용합니다. 코드베이스에는 다음의 테스트된 구현이 포함되어 있습니다:

• Beauregard modular adder -- QFT 기반 (target + constant) mod p, 적절한 보조 큐비트 언컴퓨트 포함
• Quantum-quantum modular multiply -- |a>|b>|0> -> |a>|b>|a*b mod p> (시프트 앤 애드, 명시적 모듈러 더블링), O(n^3) 게이트
• Modular inverse permutation -- |x> -> |x^{-1} mod p> (룩업 테이블 전치)
• Controlled quantum-quantum modular add -- 제어된 |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일에 발표되었습니다.

두 개의 다중 큐비트 계수 레지스터(j, k)와 대량 역 QFT를 두 개의 단일 재활용 큐비트와 고전적으로 조건화된 위상 보정으로 대체합니다. 각 계수 레지스터 비트는 순차적으로 처리됩니다: |+>로 준비, 제어된 점 덧셈 적용, 이전에 측정된 모든 비트를 기반으로 위상 보정, 그 다음 측정. Qiskit의 reset + if_test 동적 회로 프리미티브가 IBM Quantum 하드웨어에서 이를 가능하게 합니다.

제어된 점 덧셈을 위한 오라클은 기존 인프라(<= 6비트의 경우 dense unitary, > 6비트의 경우 efficient permutation)에 위임되므로, 큐비트 절약은 전적으로 계수 레지스터 제거에서 비롯됩니다.

• 인코딩: 기본 전략과 동일 (군 인덱스)
• 큐비트: 2 + n_bits + ancillas (vs 2t + n_bits + ancillas)
• 트레이드오프: 동적 회로(중간 회로 측정, 리셋, 고전적 조건 게이트)가 필요합니다. IBM Heron r2에서 최대 7비트까지 작동; 8비트 이상에서는 고전적 피드백 동기화 오버헤드가 QPU 시간 예산을 초과합니다.

전략 6: Ripple-Carry Modular Addition (--oracle ripple)

ripple_carry_shor.py에 구현되어 있습니다. 제어된 점 덧셈을 위해 CDKM ripple-carry 가산기(Cuccaro et al. 2004)를 사용하여, dense unitary 행렬과 순환 분해된 전치 회로를 모두 대체합니다.

군 인덱스 인코딩에서 점 P = kG는 순환군에서의 인덱스 k로 표현됩니다. S = sG를 더하는 것은 **고전적 상수 s의 모듈러 덧셈(mod n)**이 됩니다. 핵심 통찰: 각 제어된 점 덧셈은 알려진 상수의 단일 제어된 모듈러 덧셈으로 축소되며, Qiskit의 CDKMRippleCarryAdder와 IntegerComparator를 통해 구현됩니다.

오라클은 2m개의 제어된 모듈러 덧셈(계수 레지스터당 m개)으로 구성되며, 각 제어된 모드-덧셈은 다음을 수행합니다:

1. 상수 로드: 제어 큐비트에서 CX를 통해 보조 레지스터로 상수 로드
2. CDKM 반가산기: 보조를 누산기에 추가 (최근접 이웃 게이트만)
3. 정수 비교기: 오버플로우 감지 (acc >= n)
4. 조건부 감산: 플래그 제어 2^m1 - n 추가를 통한 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까지의 소수에 대해 상태벡터 시뮬레이션을 통해 올바르게 검증되었습니다.

결과

IBM Quantum 하드웨어에서 최대 17비트 챌린지 곡선에 대한 개인키를 성공적으로 복구했습니다:

모든 실행은 IBM Quantum 오픈 인스턴스 요금제로 수행되었으며, 이는 월 10분의 무료 양자 계산을 제공합니다. 전체 실행 로그는 executions/ 폴더에 있습니다.

리플-캐리 전략(전략 6)은 큰 도약을 가능하게 했습니다: 10비트(40큐비트, 2M 게이트)에서 **17비트(69큐비트, 112K 게이트)**로 — 7비트 키 크기 증가와 함께 2-큐비트 게이트 수가 18배 감소했습니다. CDKM 가산기의 최근접 이웃 게이트 구조는 IBM의 heavy-hex 토폴로지에 효율적으로 매핑되어 라우팅 오버헤드를 약 1배로 유지합니다.

Semiclassical PE: IBM 하드웨어에서의 동적 회로

반고전 전략(--oracle google)은 IBM Heron r2 프로세서에서 동적 회로(중간 회로 reset, if_test를 통한 고전적 조건 p 게이트)를 사용하여 4비트, 6비트 및 7비트에서 키를 성공적으로 복구했습니다. 7비트에서 회로는 14큐비트만 사용하며(표준 순열 접근 방식의 26 vs), 트랜스파일 후 비슷한 2Q 게이트 수를 생성합니다.

8비트 이상에서는 현재 IBM 하드웨어에서 반고전 접근 방식이 비실용적이 됩니다. if_else와 reset은 Heron r2에서 지원되지만(백엔드 대상 검사를 통해 확인됨), 각 고전적 피드백 지점은 전체 QPU 동기화가 필요합니다. 즉, 모든 156개의 물리적 큐비트가 유휴 상태여야 하는 동안 고전적 컨트롤러가 약 16개의 활성 큐비트에 대한 조건부를 처리합니다. 약 295K CZ 게이트가 16개 이상의 피드백 지점에 분산되어 있어, 샷당 실행 오버헤드로 인해 작업이 QPU 시간 예산을 초과합니다. 동적 회로 없이 단일 연속 배치로 동일한 게이트 수를 실행하는 표준 순열 접근 방식은 이 규모에서 성공적으로 완료됩니다.

근사 QFT 절단(max_corrections 매개변수)은 측정 단계당 가장 가까운 k개의 위상 보정만 유지함으로써 if_else 블록 수를 O(n^2)에서 O(n)으로 줄입니다(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개가 고유). 출력은 비트스트링 수준에서 균일 무작위 샘플링과 구별할 수 없습니다. 그럼에도 불구하고 알고리즘은 여전히 올바른 개인키를 복구합니다.

핵심 통찰은 쇼어의 후처리가 원시 비트스트링 분석이 그렇지 않은 방식으로 노이즈에 강건하다는 것입니다. 각 샷은 (j, k, r) 측정 트리플을 생성합니다. 추출은 d_cand = (r - j) · k^{-1} mod n을 계산하고 d_cand · G == Q를 통해 검증합니다. 진정한 d만이 EC 검증을 통과하므로, 수천 개의 노이즈 샷 중 단 하나의 올바른 후보로도 충분합니다.

순수 무작위 (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를 노이즈 플로어 위로 밀어 올립니다. 이는 계산을 불가능하게 보이게 하는 회로 충실도에도 불구하고 알고리즘이 성공하는 이유를 설명합니다.

양자 신호 vs 고전적 노이즈

장난감 규모에서 추출의 검증 단계(d_cand * G == Q)는 진정한 d만을 받아들이는 필터 역할을 합니다. 이는 순수 무작위 (j, k, r) 트리플도 실행당 약 shots / n의 비율로 유효한 후보를 생성한다는 것을 의미합니다. shots >> n일 때, 무작위 노이즈만으로도 높은 확률로 d를 복구할 수 있습니다.

양자 회로가 이 고전적 노이즈 플로어를 넘어 신호를 기여하는지 테스트하기 위해, 우리는 6비트 챌린지(n=31)에서 8샷만 사용(군 위수보다 훨씬 낮음)하여 10번 ibm_kingston에서 실행했습니다:

결과: 4/10 성공(40%) vs 고전적 노이즈 기준 약 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 큐비트를 사용한 쇼어 알고리즘 회로"](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 et al., ["양자 취약성에 대비한 타원 곡선 암호화폐 보호: 자원 추정 및 완화 방안"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## 라이선스

이 프로젝트는 Q-Day Prize Challenge 출품작으로, [MIT 라이선스](https://github.com/yuvadm/quantumslop/blob/HEAD/LICENSE) 하에 배포됩니다.