yuvadm/quantumslop타원 곡선 이산 로그 문제에 대한 양자 해결사로, 쇼어 알고리즘을 사용하며, 실제 양자 하드웨어에서 ECC 개인 키를 복구하기 위해 여러 오라클 전략을 구현합니다.
타원곡선 이산로그 문제(ECDLP)를 위한 양자 솔버로, Project Eleven이 Q-Day Prize Challenge를 위해 제작했습니다. 목표: 쇼어 알고리즘을 사용하여 실제 양자 하드웨어에서 ECC 개인키를 복구합니다.
모든 챌린지 곡선은 F_p 상에서 y^2 = x^3 + 7을 사용하며 (a = 0, b = 7), secp256k1 계열과 일치합니다. 솔버는 ECDLP를 위한 쇼어 알고리즘의 2-레지스터 변형을 구현합니다:
개인키 d는 군 위수 n에 대해 동일한 선형 관계를 만족하는 여러 (j, k) 샘플을 수집하여 복구됩니다. 솔버는 곡선 크기에 따라 자동으로 선택되거나 --oracle을 통해 수동으로 선택되는 6가지 오라클 전략을 제어된 점 덧셈에 대해 지원합니다.
군 위수가 최대 ~6 비트인 곡선에 사용됩니다. projecteleven.py에 구현되어 있습니다.
각 제어된 점 덧셈 "add S"는 qc.unitary()를 통해 적용되는 2^(n+1) x 2^(n+1) 순열 행렬로 표현됩니다. 행렬은 전체 군 작용을 인코딩합니다: 왼쪽 위 블록은 항등(제어=0), 오른쪽 아래 블록은 P -> P+S (제어=1) 매핑에 따라 기저 상태를 순열합니다.
더 큰 곡선에 사용됩니다. quantum_arithmetic.py에 구현되어 있습니다.
밀집 행렬을 구축하는 대신, 각 "add S" 순열은 전치로 순환 분해됩니다. 각 전치(두 기저 상태 |a> <-> |b>의 교환)는 다음으로 구현됩니다:
MCX는 (n-2)개의 전용 보조 큐비트를 사용하는 **V-체인 분해(V-chain decomposition)**를 사용하여, 보조 큐비트가 없을 때의 O(n^2) 대신 MCX당 O(n)개의 토폴리 게이트를 제공합니다. 각 제어된 덧셈은 고립된 서브회로로 구축되어 단일 불투명 게이트로 추가되며, Qiskit에서 이차 DAG 증가를 방지합니다.
--oracle coordinate)최대 ~6비트 곡선에 사용 가능합니다. quantum_oracle.py에 구현되어 있습니다.
점을 군 인덱스로 인코딩하는 대신, 양자 레지스터는 실제 (x, y) 체 원소 좌표를 이진수로 보유하고 항등 플래그를 추가합니다. 점 레지스터 레이아웃은 다음과 같습니다:
x_reg: f_bits qubits (f_bits = ceil(log2(p)))y_reg: f_bits qubitsid_flag: 1 qubit (1 = point at infinity)각 제어된 "add S"는 모든 유효한 좌표 인코딩에 대해 EC 덧셈 공식으로 계산되어, 좌표 레지스터에 대한 순열을 생성합니다. 이 순열은 전략 2와 동일한 CNOT 감소 + MCX 인프라를 사용하여 전치로 순환 분해됩니다.
--oracle arithmetic)다항식 스케일링 점 덧셈을 위한 프레임워크. quantum_oracle.py와 quantum_arithmetic.py에 구현되어 있습니다.
전략 3과 동일한 좌표 인코딩을 사용하며, QFT 기반 모듈러 산술 프리미티브를 완전 산술 점 덧셈을 위한 구성 요소로 사용합니다. 코드베이스에는 다음의 테스트된 구현이 포함되어 있습니다:
산술 프리미티브는 점 덧셈당 O(n^3) 스케일링을 달성하는 반면, 순열 접근 방식은 O(N*n)입니다. 그러나 QFT 기반 연산은 약 150배 더 큰 상수 요인을 가지므로, 산술 접근 방식은 약 20비트 이상의 군 위수 곡선에서만 더 효율적입니다. 현재 챌린지 크기(최대 12비트)에서는 순열 기반 가산기가 더 빠르며 기본적으로 사용됩니다.
--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)에 위임되므로, 큐비트 절약은 전적으로 계수 레지스터 제거에서 비롯됩니다.
| 곡선 크기 | 표준 큐비트 | 반고전 큐비트 | 절감율 | 하드웨어 검증 |
|---|---|---|---|---|
| 4비트 (n=7) | 11 | 5 | 55% | 예 |
| 6비트 (n=31) | 17 | 7 | 59% | 예 |
| 7비트 (n=79) | 26 + anc | 14 | 46% | 예 |
| 8비트 (n=139) | 25 + anc | 10 + anc | 60% | 아니오 (QPU 동기화 오버헤드) |
| 10비트 (n=547) | 31 + anc | 12 + anc | 61% | 아니오 (QPU 동기화 오버헤드) |
--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개)으로 구성되며, 각 제어된 모드-덧셈은 다음을 수행합니다:
회로 구성에 개인키 d에 대한 지식이 사용되지 않습니다. G-거듭제곱에 대한 군 인덱스는 2^i mod n (공개)로 계산됩니다. Q-거듭제곱에 대한 군 인덱스는 G에 의해 생성된 순환군의 공개 열거에서 파생됩니다. 점 Q는 이 열거에서 조회됩니다.
| 곡선 크기 | 큐비트 | 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 |
|---|---|---|---|---|---|---|
| 점 인코딩 | Group index | Group index | (x, y, id_flag) | (x, y, id_flag) | Group index | Group index |
| 덧셈당 스케일링 | O(4^n) decomp. | O(N * n) | O(N * f_bits) | O(n^3) asymptotic | 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비트 |
코드베이스는 256비트에서 완전 산술 좌표 인코딩을 위한 기초로 QFT 기반 모듈러 산술 구성 요소(Beauregard/Draper 가산기, 양자-양자 모듈러 곱셈, 모듈러 역/부정)를 포함합니다. 이러한 프리미티브는 p=13까지의 소수에 대해 상태벡터 시뮬레이션을 통해 올바르게 검증되었습니다.
IBM Quantum 하드웨어에서 최대 17비트 챌린지 곡선에 대한 개인키를 성공적으로 복구했습니다: