Shor의 ECDLP 알고리즘 — Q-Day Prize Submission

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

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

접근 방식

모든 챌린지 곡선은 secp256k1 계열과 일치하는 y^2 = x^3 + 7 (a = 0, b = 7)을 F_p 위에서 사용합니다. 솔버는 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: 밀집 유니타리 (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: 효율적인 순열 분해 (n_bits > 6인 경우 기본값)

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

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

1. CNOT 축소 -- 피벗 비트에서 다른 모든 다른 비트로의 CNOT, 다중 비트 차이를 단일 비트 차이로 축소
2. 다중 제어 X -- 피벗 비트에 대한 MCX 게이트, 다른 모든 비트가 대상 패턴과 일치하는 조건
3. CNOT 취소 -- 1단계를 역으로 수행하여 비-피벗 비트 복원

MCX는 (n-2)개의 전용 보조 큐비트와 함께 V-체인 분해를 사용하며, MCX당 O(n) Toffoli 게이트를 제공합니다 (보조 큐비트 없이 O(n^2) 대신). 각 제어된 덧셈은 격리된 하위 회로로 구축되어 단일 불투명 게이트로 추가되며, Qiskit에서 이차 DAG 성장을 피합니다.

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

전략 3: 좌표 기반 양자 오라클 (--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: 산술 오라클 (--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>, 시프트-앤-애드 방식과 명시적 모듈러 배가, O(n^3) 게이트
• 모듈러 역원 순열 -- |x> -> |x^{-1} mod p>, 룩업 테이블 전치를 통해
• 제어된 양자-양자 모듈러 덧셈 -- |a> -> |a + b mod p>, Beauregard 축소 포함

산술 프리미티브는 순열 접근 방식의 O(N*n) 대신 점 덧셈당 O(n^3) 크기 조정을 달성합니다. 그러나 QFT 기반 연산은 ~150배 더 큰 상수 인자를 가지므로 산술 접근 방식은 ~20비트 군 차수 이상의 곡선에서만 더 효율적입니다. 현재 챌린지 크기(최대 12비트)의 경우 순열 기반 가산기가 더 빠르며 기본적으로 사용됩니다.

전략 5: Google 반고전적 위상 추정 (--oracle google)

google_semiclassical.py에 구현되어 있습니다. Babbush et al. (2026)에서 secp256k1 ECDLP 자원 추정을 위해 확장되어 적용된 Griffiths & Niu (1996)의 큐비트 재활용 위상 추정 기술에서 영감을 받았습니다. Babbush et al. 논문은 2026년 3월 30일에 발표되었습니다.

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

제어된 점 덧셈을 위한 오라클은 기존 인프라(<= 6비트의 경우 밀집 유니타리, > 6비트의 경우 효율적 순열)에 위임되므로 큐비트 절감은 전적으로 계수 레지스터를 제거함으로써 발생합니다.

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

전략 6: 리플-캐리 모듈러 덧셈 (--oracle ripple)

ripple_carry_shor.py에 구현되어 있습니다. 제어된 점 덧셈에 CDKM 리플-캐리 가산기(Cuccaro et al. 2004)를 사용하며, 밀집 유니타리 행렬과 주기 분해 전치 회로를 모두 대체합니다.

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

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

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 토폴로지에서 ~1x 라우팅 오버헤드 (QFT 기반 가산기의 26-33x 대비)

비교

QFT 산술 프리미티브

코드베이스에는 완전 산술 좌표 인코딩을 256비트로 확장하기 위한 기반으로 QFT 기반 모듈러 산술 구성 요소(Beauregard/Draper 가산기, 양자-양자 모듈러 곱셈, 모듈러 역원/부정)가 포함되어 있습니다. 이러한 프리미티브는 p=13까지의 소수에 대해 Statevector 시뮬레이션을 통해 올바른 것으로 검증되었습니다.

결과

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

모든 실행은 IBM Quantum 오픈 인스턴스 플랜에서 수행되었으며, 이는 월 10분의 무료 양자 컴퓨팅 시간을 제공합니다. 전체 실행 로그는 executions/ 폴더에 있습니다.

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

반고전적 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 동기화가 필요합니다 — 모든 156개의 물리적 큐비트가 고전적 컨트롤러가 ~16개 활성 큐비트에 대한 조건부를 처리하는 동안 유휴 상태여야 합니다. 16개 이상의 피드백 지점에 걸쳐 분할된 ~295K CZ 게이트를 사용하면 샷당 실행 오버헤드로 인해 작업이 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개 고유). 출력은 비트스트링 수준에서 균일 무작위 샘플링과 구별할 수 없습니다. 그럼에도 알고리즘은 여전히 올바른 개인 키를 복구합니다.

핵심 통찰은 Shor의 사후 처리가 원시 비트스트링 분석이 할 수 없는 방식으로 잡음에 강건하다는 것입니다. 각 샷은 (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를 잡음 바닥 위로 밀어 올립니다. 이것은 계산을 불가능하게 할 것 같은 회로 충실도에도 불구하고 알고리즘이 어떻게 성공하는지 설명합니다.

양자 신호 대 고전적 잡음

장난감 규모에서 추출의 검증 단계(d_cand * G == Q)는 진짜 d만을 받아들이는 필터 역할을 합니다. 즉, 순수한 무작위 (j, k, r) 삼중항조차도 실행당 대략 shots / n의 비율로 유효한 후보를 생성합니다. shots >> n일 때 무작위 잡음만으로도 높은 확률로 d를 복구할 수 있습니다.

양자 회로가 이 고전적 잡음 바닥 이상으로 신호에 기여하는지 테스트하기 위해 우리는 6비트 챌린지 (n=31)을 단 8개 샷(군 차수보다 훨씬 낮음)으로 10번 ibm_kingston에서 실행했습니다:

결과: 10회 중 4회 성공 (40%) 대 고전적 잡음 기준선 ~20% (Monte Carlo 시뮬레이션을 통해 계산: 검증을 통해 필터링된 (r-j)*k_inv mod 31을 사용한 8개의 무작위 비트스트링). 단측 이항 검정: 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 외., ["양자 취약점으로부터 타원 곡선 암호화폐 보호: 자원 추정 및 완화 방안"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## 라이선스

이 프로젝트는 Q-Day Prize Challenge에 제출된 결과물로, [MIT 라이선스](https://github.com/giancarlolelli/quantum/blob/HEAD/LICENSE)에 따라 배포됩니다.