1. 문제 정의 (Problem)

• 양자 컴퓨팅의 위협: 쇼어 알고리즘 (Shor's algorithm) 은 타원곡선 이산 로그 문제 (ECDLP) 를 다항 시간 내에 해결할 수 있어, 비트코인이 사용하는 ECDSA (secp256k1) 와 같은 현대 암호체계를 무력화할 수 있습니다.
• 진행 상황 추적의 부재: 양자 컴퓨터의 발전, 특히 오류 정정 양자 컴퓨터 (FTQC) 의 실용화 시점을 예측하기 위해 필요한 정량적인 기준이 부족합니다.
  • 기존 벤치마크 (Certicom ECC 챌린지 등) 는 데이터가 너무 희소하여 연도별 진전을 세밀하게 추적하기 어렵습니다.
  • 비트코인 퍼즐 (Bitcoin puzzles) 은 키가 특정 구간으로 제한된 경우 (Pollard's kangaroo 알고리즘 대상) 에만 해당되며, 쇼어 알고리즘이 해결해야 하는 전체 군 (Group) 에 대한 문제와는 다릅니다.
• 불확실성: 현재 어떤 수준의 물리적 자원이 필요하며, 언제 비트코인 주소의 개인키가 위협받을지 명확한 로드맵이 부재합니다.

2. 방법론 (Methodology)

저자들은 비트코인의 타원곡선 형태 ($y^2 = x^3 + 7 \pmod p$) 를 유지하면서, 소수 필드 (prime field) 의 크기를 256 비트에서 6 비트까지 점진적으로 줄이는 난이도 등급 챌린지 스위트 (Difficulty-graded suite) 를 제안했습니다.

• 챌린지 생성 (Deterministic Construction):
  • 각 비트 길이 ($k \in \{6, \dots, 256\}$) 에 대해 소수 $p$, 소수 군 차수 $n$, 그리고 두 개의 결정론적 NUMS (Nothing-Up-My-Sleeve) 점 $P, Q$를 생성합니다.
  • 비밀 스칼라를 미리 선택하지 않고, "Quantum"과 "Challenge"라는 고정된 ASCII 라벨을 SHA256 해싱하여 점의 좌표를 유도합니다. 이는 모든 결과가 재현 가능하고 투명함을 보장합니다.
  • 모든 챌린지는 secp256k1 의 수학적 구조를 그대로 따르되, 필드 크기만 축소합니다.
• 고전적 비용 교정 (Classical Calibration):
  • Pollard's rho 알고리즘을 사용하여 고전 컴퓨터로 해결 가능한 한계를 분석합니다.
  • 기존 기록 (112~129 비트 구간) 을 기준으로 하여, 고전적 접근의 한계 (약 120 비트 이상은 실용적이지 않음) 를 설정합니다.
• 양자 자원 추정 (Quantum Resource Estimation):
  • 쇼어 알고리즘을 타원곡선에 적용하기 위한 논리적 회로 (Logical Circuit) 를 컴파일합니다.
  • 논리적 자원을 물리적 자원으로 매핑하기 위해 세 가지 오류 정정 코드를 비교 분석했습니다:
    1. Surface Code (표면 코드): 격자 수술 (Lattice surgery) 기반의 표준 2D 아키텍처.
    2. Repetition Cat Code: Alice & Bob 의 보손적 (bosonic) 큐비트 기반, 비트 플립이 억제된 비대칭 잡음 모델.
    3. LDPC Cat Code: 저밀도 패리티 검사 (LDPC) 코드와 Cat 큐비트를 결합한 고율 (High-rate) 아키텍처.
  • 물리적 게이트 오류율, 코드 거리, 마법 상태 (Magic state) 공급 능력 등 명시적인 가정을 바탕으로 256 비트 인스턴스를 해독하는 데 필요한 물리적 큐비트 수와 실행 시간을 계산했습니다.

3. 주요 기여 (Key Contributions)

1. 재현 가능한 챌린지 사다리 (Challenge Ladder): 6 비트 (수동 해결 가능) 에서 256 비트 (실제 비트코인) 까지 이어지는 일련의 ECDLP 인스턴스를 공개했습니다. 이는 알고리즘 개발자, 하드웨어 엔지니어, 시스템 설계자가 공통의 자를 사용하여 진전을 측정할 수 있게 합니다.
2. 정교한 자원 추정 모델: 단순한 논리적 큐비트 수 계산을 넘어, 다양한 오류 정정 코드 (Surface, Cat, LDPC) 에 따른 물리적 자원 (물리적 큐비트 수, 실행 시간, Toffoli 게이트 수) 을 상세히 매핑했습니다.
3. 시각적 로드맵: 알고리즘의 발전과 하드웨어의 로드맵 (IBM, Google, Quantinuum 등) 을 하나의 공통 척도 위에 겹쳐서, 암호분석에 유의미한 양자 컴퓨터 (CRQC) 가 등장할 시기를 예측했습니다.
4. 비트코인 이전 전략 제안: 위험이 현실화되기 전에 디지털 자산을 양자 내성 (Post-Quantum) 서명으로 이전해야 한다는 구체적인 기술적, 경제적 논거를 제시했습니다.

4. 주요 결과 (Results)

• 고전적 한계: 고전 컴퓨터는 Pollard's rho 알고리즘으로 인해 비트 길이가 약 120 비트를 넘어서면 실용적인 시간 내에 해결이 불가능해집니다.
• 양자 자원 추정 (256 비트 인스턴스 기준):
  • Surface Code (보수적 가정): 수백만 개의 물리적 큐비트와 수일~수주 소요.
  • Surface Code (공격적 가정): 수십만 개 물리적 큐비트와 수 시간 소요.
  • Repetition Cat Code: 약 126,000 개의 Cat 큐비트로 약 9 시간 소요.
  • LDPC Cat Code: 약 38,000 개의 Cat 큐비트로 수 시간~하루 소요.
• 예상 타임라인: 현재 알고리즘 발전 속도와 하드웨어 로드맵을 종합할 때, 비트코인 secp256k1 을 해독할 수 있는 오류 정정 양자 컴퓨터는 2027 년에서 2033 년 사이에 등장할 가능성이 높습니다.
  • 이 시기는 "Megaquop" (약 100 만 논리적 연산) 기계가 실현되는 시기와 일치합니다.
• 중간 단계의 중요성: 6 비트나 160 비트와 같은 중간 단계 챌린지가 성공적으로 해결되는 것은 전체 시스템의 성숙도를 검증하는 중요한 마일스톤이 될 것입니다.

5. 의의 및 시사점 (Significance)

• 투명한 경고 시스템: 이 챌린지 스위트는 양자 암호분석의 진전을 투명하게 추적할 수 있는 "공유된 자 (Ruler)" 역할을 합니다. 이는 기술적 불확실성을 줄이고, 조기 경보 시스템을 구축하는 데 기여합니다.
• 비트코인의 생존 전략: 비트코인 주소의 공개 키가 체인에 노출되면 쇼어 알고리즘에 의해 개인키가 유출될 수 있습니다. 저자들은 Commit-then-upgrade 전략을 제안합니다.
  • 현재는 기존 서명을 유지하되, 양자 내성 서명으로의 이전을 약속하는 해시 (Commit) 를 스크립트에 포함시키는 방식입니다.
  • 양자 위협이 임박했을 때 소프트 포크를 통해 양자 내성 검증 (PQSIGVERIFY 등) 을 활성화하고, 자산을 안전한 주소로 이동시킬 수 있습니다.
• 정책적 권고: 기술적 도약이 예상보다 빨라질 수 있으므로, 지금 당장 양자 내성 서명으로의 이전 계획을 수립하고 실행하는 것이 "저렴한 보험"이라고 강조합니다.

결론적으로, 이 논문은 양자 컴퓨팅이 비트코인 등 현대 암호체계에 미칠 위협을 정량화하고, 이를 측정할 수 있는 구체적인 기준을 제시하며, 이에 대응하기 위한 기술적·정책적 로드맵을 제시한 중요한 연구입니다.