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-레지스터 변형을 구현합니다:

계수 레지스터 |j>, |k>를 균일 중첩으로 준비 (Hadamard)
2t개의 제어된 점 덧셈 (t = num_counting qubits)을 통해 |j>|k>|jG + kQ> 계산
점 레지스터를 측정하여 일부 군 원소 R로 붕괴
계수 레지스터에 역 QFT 적용
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>의 교환)는 다음으로 구현됩니다:

CNOT 축소 -- 피벗 비트에서 다른 모든 다른 비트로의 CNOT, 다중 비트 차이를 단일 비트 차이로 축소
다중 제어 X -- 피벗 비트에 대한 MCX 게이트, 다른 모든 비트가 대상 패턴과 일치하는 조건
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비트의 경우 효율적 순열)에 위임되므로 큐비트 절감은 전적으로 계수 레지스터를 제거함으로써 발생합니다.

곡선 크기	표준 큐비트	반고전적 큐비트	절감율	하드웨어 검증
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 + 보조 큐비트 (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개)으로 구성되며, 각 제어된 모드-덧셈은 다음을 수행합니다:

상수 로드 -- 제어 큐비트에서 CX를 통해 보조 레지스터로
CDKM 반가산기 -- 보조 레지스터를 누산기에 추가 (최근접 이웃 게이트만)
정수 비교기 -- 오버플로우 감지 (acc >= n)
조건부 n 빼기 -- 플래그 제어를 통해 2^m1 - n 추가
플래그 언컴퓨트 -- 캐리 기반 프로빙을 통해

회로 구성에 개인 키 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 대비)

곡선 크기	큐비트	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	예

비교

메트릭	밀집 유니타리	효율적 순열	좌표 오라클	산술 오라클	반고전적 PE	리플-캐리
점 인코딩	군 인덱스	군 인덱스	(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 시뮬레이션을 통해 올바른 것으로 검증되었습니다.

결과

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

quantum

인기