⚛️ quantum physics

ECDSA.Fail: Open Autoresearch for Optimizing Elliptic-Curve Point Addition in Shor's Algorithm

이 논문은 쇼어 알고리즘을 위한 가역적 secp256k1 점-덧셈 회로를 성공적으로 최적화하여, 시공간 비용을 86.1% 절감하고 ECDSA를 해독하기 위한 구글의 발표된 효율성 임계치를 넘어선 인간-AI 협업 패러다임인 "Open Autoresearch"를 소개한다.

원저자: Jieyi Long, Theodore Pender, Zhao Huang, Manuel B. Santos, Samrendra Kumar Singh, Bartosz Naskręcki, Bit Wonka, Joe Doyle, Pierre-Luc Dallaire-Demers, Francesco Giannicola, Ruben M. L. Paschoarelli, O

게시일 2026-09-10

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Jieyi Long, Theodore Pender, Zhao Huang, Manuel B. Santos, Samrendra Kumar Singh, Bartosz Naskręcki, Bit Wonka, Joe Doyle, Pierre-Luc Dallaire-Demers, Francesco Giannicola, Ruben M. L. Paschoarelli, Oli Freuler, Jackie Chia-Hsun Lee, Vasily Gnuchev, Gopi Kannappan, John Boyer, Xavier Butler, Akash Balasubramani, Jordan Newman, Bereket Dereje, Alexander Hertlein, Robert Kodra, Lucas Levy, Shaan Patel, JT Rose, Matt Zweil, Okechukwu Wisdom, Tarek El-Eter, Edison Lee, Michael Dong, Alan Li, Anto Joseph, Gajesh Naik, Gautham Anant, Soubhik Deb, Justin Drake

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

현대 보안의 세계에서 우리의 많은 디지털 잠금장치는 곡선 위의 점들과 관련된 수학적 퍼즐에 의존하고 있습니다. 이 퍼즐은 오늘날의 컴퓨터가 풀기에는 너무나 어려워 은행 계좌부터 디지털 통화인 비트코인에 이르기까지 모든 것을 보호하고 있습니다. 그러나 과학자들은 양자 역학의 기묘한 법칙을 사용하는 미래형 컴퓨터라면 현재 우리가 가진 어떤 기계보다 훨씬 빠르게 이 퍼즐을 풀 수 있다는 사실을 오래전부터 알고 있었습니다. 이러한 기계를 구축하는 데 얼마나 가까이 다가갔는지 이해하기 위해, 연구자들은 이를 위해 필요한 자원을 추정하려고 노력합니다. 그들은 이 잠금장치를 깨뜨리는 데 얼마나 많은 큐비트(qubit)라고 불리는 작은 양자 비트와 얼마나 많은 복잡한 논리적 단계가 필요한지를 계산합니다. 이 추정치는 우리가 기존의 보안 체계가 무너지기 전에 새로운, 깨뜨릴 수 없는 보안 시스템으로 언제 전환해야 하는지를 알려주는 중요한 지표가 됩니다.

ECDSA.Fail이라는 새로운 프로젝트는 이 문제를 해결하기 위해 새로운 접근 방식을 취하여, 더 나은 양자 설계를 찾는 과정을 공개 경쟁으로 전환했습니다. 단일 팀이 비밀리에 작업하는 대신, 수백 명의 사람과 인공지능 에이전트가 타원 곡선 퍼즐을 깨뜨리는 데 필요한 특정 양자 코드의 일부를 개선하기 위해 협력했습니다. 목표는 양자 컴퓨터의 동작을 위한 청사진인 회로를 최대한 효율적으로 만드는 것이었습니다. 연구진은 두 가지 측면, 즉 회로를 실행하는 데 동시에 필요한 큐비트의 수와 수행되는 총 복사 연산의 수를 살펴봄으로써 효율성을 측정했습니다. 그들은 이 두 숫자를 곱하여 하나의 점수를 산출했는데, 이 점수가 낮을수록 더 효율적인 설계임을 의미했습니다.

이 공개적인 협업의 결과는 놀라웠습니다. 팀은 2,000개 이상의 큐비트와 거의 400만 개의 연산을 필요로 하는 기본 설계에서 시작했습니다. 참가자들이 최선의 아이디어를 공유하고 AI 에이전트가 수천 가지의 변형을 테스트하며 지속적으로 개선해 나가는 과정을 통해, 그룹은 효율성 점수를 86% 이상 삭감하는 데 성공했습니다. 데이터가 수집되었을 때, 가장 우수한 설계는 약 1,150개의 큐비트와 대략 130만 개의 연산만을 필요로 했습니다. 이 새로운 기록은 자신의 구체적인 회로 설계를 숨겨왔던 구글의 연구 그룹을 포함한 주요 연구 그룹들의 이전 추정치보다 현저히 뛰어납니다. ECDSA.Fail 팀은 회로를 더 작고 빠르게 만듦으로써 이를 달 achievement 했으며, 이는 인간과 기계가 함께 협력하는 공동체가 고립된 전문가들보다 복잡한 공학 문제를 더 빠르게 해결할 수 있음을 증명했습니다.

이 프로젝트는 단순히 더 나은 숫자를 찾아낸 것에 그치지 않고, 서로 다른 전략들이 어떻게 작동하는지를 보여주었습니다. 한 그룹의 참가자들은 회로를 최대한 작게 만드는 데 집중하여, 단 825개의 큐비트만을 사용하도록 압축했습니다. 이 버전은 훨씬 적은 양의 큐비트를 사용했지만, 실행하는 데 훨씬 더 많은 연산이 필요했는데, 이는 공간과 시간 사이의 명확한 상충 관계를 보여주었습니다. 또 다른 그룹은 전반적인 점수에 집중하여, 가장 효율적인 경로를 찾기 위해 두 요소를 균형 있게 조절했습니다. 연구진은 또한 가장 우수한 설계를 바탕으로 양자 알고리즘을 실행하는 더 발전된 방식으로 작동할 수 있는 버전을 구축하여, 이러한 개선이 단지 이론적인 것에 그치지 않고 실제 환경에 적용될 수 있음을 보여주었습니다.

이 성과를 특히 주목할 만하게 만드는 것은 그 도달 방법입니다. 연구진은 누구나 설계를 제출할 수 있고, 컴퓨터 프로그램이 즉시 그것이 올바르게 작동하는지 확인하고 점수를 계산할 수 있는 시스템을 만들었습니다. 이를 통해 인공지능 에이전트들이 인간의 지속적인 감독 없이도 제안하고, 테스트하고, 실패로부터 배우는 지칠 줄 모르는 연구자로서 역할을 할 수 있었습니다. 인간은 전체적인 방향을 결정하고 아이디어를 추구할지 판단하며 결과를 해석하는 데 개입했습니다. 이 프로젝트는 문제가 기계에 의해 빠르고 정확하게 검증될 수 있을 때, 인간과 AI의 다양한 집단이 전통적인 연구 팀을 능가할 수 있음을 보여주었습니다.

또한 이 논문은 이러한 결과가 미래에 무엇을 의미하는지 명확히 하고 있습니다. 새로운 설계들이 훨씬 더 효율적이기는 하지만, 아직 현재의 암호 체계를 깰 수 있는 완전한 청사진은 아닙니다. 테스트된 회로들은 훨씬 더 큰 퍼즐의 한 조각일 뿐이며, 전체 시스템은 여전히 막대한 양의 오류 수정과 아직 존재하지 않는 물리적 하드웨어를 필요로 합니다. 게다가, 설계들은 제대로 작동하는지 확인하기 위해 특정 입력 세트에 대해 테스트되었으며, 모든 가능한 시나리오에서 완벽하게 작동한다는 보장은 없습니다. 연구진은 이것이 문제에 대한 이론적 이해를 개선한 것이지, 잠금장치가 내일 당장 깨질 것이라는 경고가 아님을 신중하게 밝히고 있습니다.

궁극적으로 ECDSA.Fail 프로젝트는 과학이 개방적이고 협력적일 때 어떻게 진화할 수 있는지를 보여주는 강력한 증거입니다. 문제를 공개하고 결과를 검증 가능하게 함으로써, 팀은 누구나 공부할 수 있는 진보의 살아있는 기록을 만들었습니다. 그들은 어려운 문제를 해결하는 길이 더 이상 개인의 천재성에 의존하는 것이 아니라, 인간의 통찰력과 기계의 속도가 서로를 강화할 수 있는 시스템을 구축하는 것임을 보여주었습니다. 세상이 양자 컴퓨터가 있는 미래로 나아감에 따라, 이러한 종류의 개방적이고 투명한 연구는 위험을 이해하고 우리의 디지털 세계를 보호하기 위한 방어책을 준비하는 데 필수적일 것입니다.

기술 요약: ECDSA.Fail: 쇼어 알고리즘(Shor's Algorithm)을 위한 타원 곡선 점 덧셈 최적화의 오픈 오토리서치(Open Autoresearch)

1. 문제 정의

본 논문은 타원 곡선 이산 로그 문제(ECDLP)를 해결하기 위한 쇼어 알고리즘의 핵심 병목 구간인 **타원 곡선 점 덧셈(elliptic-curve point addition)**을 위한 가역적 양자 회로(reversible quantum circuits)의 최적화를 다룬다. 구체적으로는 비트코인과 이더리움의 기반이 되는 secp256k1 곡선에 초점을 맞춘다.

주요 목표는 시공간 영감형 비용 지표인 $S = Q \times T$ 를 최소화하는 것이다. 여기서:

$Q$ : 피크 논리 큐비트 폭(space, 공간).
$T$ : 평균 실행된 토폴리 게이트(Toffoli gate) 수(non-Clifford work, 작업량).

벤치마크 과제는 가역적 혼합 점 덧셈(reversible mixed point-addition) 회로( $R \leftarrow R + A$ )를 구현하는 것이다. 여기서 누산기(accumulator) $R$ 은 양자 데이터이며, 더해지는 값(addend) $A$ 는 클래식하게 지정된다. 이 회로는 쇼어 알고리즘과 같은 더 큰 코히어런트(coherent) 알고리즘 내에서 올바르게 작동하기 위해 "클린(clean)"해야 하며(보조 큐비트가 $|0\rangle$ 로 복귀), "위상 클린(phase-clean)"해야 한다(잔여 위상이 없음).

2. 방법론: 오픈 오토리서치(Open Autoresearch)

본 논문은 **오픈 오토리서치(Open Autoresearch)**라는 새로운 연구 패러다임을 도입하고 구체화한다. 개별 전문가나 소규모 팀에 의해 주도되는 전통적인 연구와 달리, 이 방식은 공공 리더보드를 통해 경쟁하고 협업하는 인간과 AI 에이전트의 이질적인 커뮤니티를 포함한다.

메커니즘: 참가자들은 공유 저장소에 회로 수정 사항을 제안한다. 이들은 클래식한 정확성, 보조 큐비트의 청결성, 그리고 피아트-샤미르 해싱(Fiat-Shamir hashing)을 통해 유도된 결정론적 제출 의존 테스트 세트에 대한 위상 청결성을 검증하는 **기계 검증 가능 평가기(machine-checkable evaluator)**에 의해 평가된다.
프로세스: 검증된 개선 사항은 추가 최로직을 위한 공공 "베이스(bases)"가 된다. 이 과정은 개방적이고 관찰 가능하며 누적적이다. 이를 통해 독립적인 인간-에이전트 팀이 사전 조율 없이도 서로의 작업 위에 구축할 수 있다.
도구: 참가자들은 가설 생성, 코드 구현, 디버깅을 위해 대규모 언어 모델(LLM) 에이전트(예: Claude Code, Codex)를 활용하였으며, 고수준의 전략 및 도메인 제약 조건에 따라 인간의 스티어링(steering)을 받았다.

3. 주요 기여

A. 오픈 오토리서치 패러다임

본 논문은 다음을 포함하는 프레임워크를 정형화한다:

검증 가능한 목표: 문제는 효율적으로 계산 가능하고 기계로 검증 가능한 지표에 의해 정의된다.
누적적 탐색: 독립적인 에이전트들이 성공과 실패의 공유된 공공 기록에 기여한다.
인간-에이전트 시너지: 인간은 아키텍처 방향을 제시하고 결과를 해석하는 역할을 수행하며, 에이전트는 구현, 반복적인 실험, 국소적 최적화를 담당한다.
본 논문은 평가 비용이 저렴하고 신뢰할 수 있는 프런티어 최적화 문제에 이 모델이 효과적이라고 주장한다.

B. 프런티어 수준의 회로 최적화

이 챌린지는 secp256k1 점 덧셈에 대한 자원 추정치를 크게 감소시키는 성과를 냈다. 주요 아키텍처 혁신은 다음과 같다:

Jump-2 유클리드 알고리즘: 연속적인 유클리드 단계를 매크로 단계로 그룹화하여 비교 및 스왑 횟수를 줄이는 다이얼로그-GCD(dialog-GCD, 기록 및 재생) 알고리즘의 리타이밍 기법이다.
Base-5 트랜스크립트 코덱(Transcript Codec): 세 개의 Jump-2 심볼(8개 중 5개의 유효 상태만 가짐)을 9개의 큐비트 대신 7-큐비트 레지스터에 인코딩하여, 가역적 재생에 필요한 트랜스크립트 저장 공간을 크게 줄이는 압축 기술이다.
비교 없는 핑퐁 다이얼로그-GCD(Comparison-Free Ping-Pong Dialog-GCD): 전체 폭의 크기 비교를 제거하기 위해 저비트 패리티 체크와 교대 업데이트 방향을 사용하는 포스트 컷오프(post-cutoff) 아키텍처로, 토폴리 수를 줄이기 위해 큐비트 폭을 트레이드오프한다.
레지스터 공유 확장 유클리드 알고리즘(EEA): 줄어드는 나머지(remainder)와 커지는 베주(Bézout) 계수를 공유 물리 뱅크에 패킹하는 공격적인 레지스터 공유 전략(Luo 등과 TrailMix에서 유도됨)을 통해 극단적인 폭 감소를 실현한다.
특화된 산술 연산: 중복 연산을 제거하기 위해 의사 메르센(pseudo-Mersenne) 모듈로 감소 및 상수 전파를 적용한 카츠마라(Karatsuba) 제곱 연산 구현.

C. 포괄적인 공공 기록

본 프로젝트는 400개 이상의 승인된 제출물에 대한 완전하고 감사 가능한 소스 기록을 공개하였다:

자원 개선의 전체 궤적.
최적화 메커니즘(예: 데드 코드 제거, 레지스터 할당, 알고리즘 치환)에 따른 400개 수락된 커밋의 분류.
모든 보고된 동작 지점(operating points)의 독립적 검증을 허용하는 재현 가능한 아티팩트.

4. 결과

성능 지표

데이터 컷오프(2026년 7월 26일) 시점에서, 챌린지는 다음을 달성했다:

베이스라인: $Q = 2,715$ , $T = 3,960,753$ , $S \approx 10.75$ 빌리언.
최고 $Q \times T$ 회로 (8e9c9a2): $Q = 1,151$ 및 $T = 1,299,453$ 으로 감소하여 $S \approx 1.496$ 빌리언을 달성했다.
- 이는 점수에서 86.1%의 감소를 나타낸다.
- 이 점수는 이전에 보고된 Google/Babbush 등의 동작 지점(약 2.993B)보다 50% 이상 낮다.
최고 저큐비트(Low-Qubit) 회로 (b6f2b0a): $T \approx 4.89$ 억과 함께 $Q = 825$ 를 달성했다(이후 컷오프 후 제출물에서 813으로 개선됨).
컷오프 후 개선: "핑퐁(ping-pong)" 변형(3616dbf)은 점수를 $S \approx 1.259$ 빌리언 ( $Q=1,321, T=952,707$ )까지 더욱 낮추었다.

이전 연구와의 비교

최고의 $Q \times T$ 회로는 $Q$ 와 $T$ 축 모두에서 Google/Babbush 및 Schrottenloher가 보고한 동작 지점보다 아래에 위치한다. 본 논문은 수치적 점수는 더 우수하지만, 인터페이스의 차이(본 벤치마크는 클래식한 더해지는 값을 사용하지만, 윈도우 방식의 쇼어는 코히어런트한 더해지는 값을 사용함)와 회계 관례로 인해 완전한 우위(formal dominance)를 확언할 수는 없다고 언급한다.

윈도우 호환성(Windowed Compatibility)

저자들은 최고 점수를 기록한 회로의 **윈도우 추가 호환 변형(windowed-addition-compatible variant)**을 구축하였다. 이 변형은 QROM을 통해 더해지는 값을 코히어런트하게 수용하며, 11개의 큐비트와 약 29.6%의 토폴리 오버헤드가 추가된다. 이는 $\hat{p} \approx 0.998$ 의 경험적 성공 확률을 유지하며, 재시도 조정된 프록시 점수는 약 1.961 빌리언으로, 여전히 Google/Schrottenloher의 지점보다 낮다.

5. 의의 및 주장

본 논문은 두 가지 영역에서 의의를 주장한다:

암호학적 자원 추정: 결과는 컷오프 시점 기준으로 secp256k1 점 덧셈에 대해 보고된 가장 낮은 수치의 $Q \times T$ 점수를 제공한다. 이 수치들은 타원 곡선 암호론을 깨기 위해 암호학적으로 유의미한 양자 컴퓨터(CRQC)가 필요로 하는 논리적 자원에 대한 이해를 정교화한다. 다만, 본 논문은 이것이 물리적 오류 정정, 라우팅, 전체 쇼어 통합을 생략한 완전한 결함 허용 자원 추정치가 아님을 명시적으로 밝힌다.
방법론적 검증: 본 논문은 ECDSA.Fail을 **오픈 오토리서치(Open Autoresearch)**의 첫 번째 대규모 시연으로 제시한다. 이는 다음을 입증한다:
- 인간과 AI 에이전트 커뮤니티가 고립된 팀보다 더 빠르게 어려운 최적화 문제를 집단적으로 해결할 수 있다.
- 개방형 공유, 기계 검증 가능성, 에이전트 규모의 실험의 결합이 누적적인 연구 프로세스를 생성한다.
- 인간의 판단은 스티어링, 결과 해석, 개념적 간극을 메우는 데 여전히 필수적이지만, 에이전트는 구현과 반복적인 정교화에 탁월하다.

저자들은 결과가 특정 벤치마크 상의 동작 지점이며 유한한 검증 지원을 받는다는 점을 강조하며 겸허한 입장을 유지한다. 그들은 secp256k1을 깨뜨렸거나 확정적인 "Q-day" 타임라인을 설정했다고 주장하는 것이 아니라, 미래의 자원 추정 및 양자 내성 전환 계획을 위한 투명하고 재현 가능하며 크게 개선된 베이스라인을 제공하고자 한다.