Alice & Bob, 약 2만 3천 개의 캣 큐비트로 RSA-2048 해독 가능하다는 새 추정치 발표

파리와 보스턴에 본사를 두고 캣 큐비트(cat qubit) 기반 양자컴퓨터를 개발하는 Alice & Bob은 10월 29일, 자사 아키텍처로 구축한 내결함성 기계가 물리 큐비트 22,593개로 3.14일 만에 2048비트 RSA 키를 소인수분해할 수 있다는 자원 추정치를 발표했다. 회사는 이 결과가 오늘날의 공개키 암호를 상대로 쇼어 알고리즘을 실행하는 데 필요한 총 양자 자원(큐비트 수 × 실행 시간)의 새로운 최저 기록이라고 설명한다. 이 연구는 프리프린트로 공개된 이론적 전망이며 하드웨어 시연이 아니다.

발표 내용

수치는 논문 "Shor's algorithm compiled on cat qubits: 22 593 qubits for RSA-2048 in 3.14 days"에서 나왔으며, Alice & Bob 연구팀과 Inria 및 렌 대학교 소속 공동 저자 한 명이 IACR의 Cryptology ePrint Archive에 게시했다. RSA-2048 외에도 연구팀은 비트코인과 이더리움 서명의 수학적 기반인 256비트 타원곡선 이산로그 문제(ECDLP)를 최대 29,588개의 물리 큐비트로 61.8분 만에 풀 수 있다고 추정했다. 또한 약 6,700 큐비트와 21분이 필요한 더 작은 벤치마크인 FFDLP-512도 제안했다.

회사 발표에 따르면 이 RSA 수치는 Google Quantum AI의 Craig Gidney가 내놓은 2025년 추정치보다 물리 큐비트가 40배 적다. Gidney의 추정은 표면 코드 기계에서 RSA-2048에 100만 개 미만의 잡음 큐비트와 1주일 미만의 실행 시간이 필요하다고 보았다.

DesignQuantum 뉴스레터 구독하기

양자 컴퓨팅 뉴스와 해설을 무료로 받아보세요. 모든 주장에는 출처 링크가 있습니다. 매일, 매주 또는 매월 중에서 선택하세요.

Website

이메일 주소 발송 빈도매일매주매월 언어EnglishEspañol简体中文हिन्दीالعربيةPortuguês (Brasil)FrançaisDeutsch日本語Русский한국어Bahasa IndonesiaTürkçeItalianoTiếng ViệtPolskiNederlandsไทยفارسیУкраїнськаবাংলাاردوKiswahiliBahasa Melayuעברית 무료 구독

무료입니다. 언제든 클릭 한 번으로 구독을 해지할 수 있습니다. 개인정보 처리방침

기술적 세부 사항

저자들은 논리 큐비트 수에 평균 오버헤드를 곱하는 대신, 알고리즘에서 가장 비용이 큰 부분을 개별 물리 큐비트 연산 수준까지 컴파일해 완전한 칩 레이아웃과 스케줄을 만들었다. Alice & Bob은 절감 효과를 세 가지 요소로 설명한다. 첫째, 캣 큐비트가 하드웨어에서 비트 플립 오류를 억제하므로 오류 정정은 위상 플립 오류만 처리하면 된다. 둘째, LDPC-cat 코드로, 회사에 따르면 이전의 반복 코드 방식에 비해 RSA-2048에 필요한 큐비트 수를 절반 이상(49,649개에서 22,593개로) 줄인다. 셋째, 오류 정정을 기다리지 않고 일정한 속도로 동작하도록 캣 큐비트용으로 재설계한 덧셈기다. 알고리즘 측면에서는 Google과 Inria 연구진의 최근 연구를 활용했다.

가정이 중요하다. 논문은 1마이크로초의 오류 정정 주기, 10마이크로초의 반응 시간, 5 × 10⁻⁴의 위상 오류 확률, 그리고 비트 플립이 전혀 없는 상황(약 100년의 비트 플립 시간에 해당)을 가정한다. 비트 플립이 대략 한 시간에 한 번 발생한다면 추가 인코딩 계층이 필요하며, RSA-2048 추정치는 약 45,000 큐비트로 늘어난다. 이 설계는 공간과 시간을 맞바꿀 수도 있어, 약 611,000 큐비트를 쓰면 RSA 실행이 1.25시간으로 줄고, 약 21,188 큐비트를 쓰면 8.08일로 늘어난다.

왜 중요한가

오류 정정과 알고리즘 설계가 발전하면서 쇼어 알고리즘의 자원 추정치는 계속 낮아지고 있으며, 그때마다 보안팀이 계획에 쓰는 시간표가 짧아진다. Alice & Bob은 하드웨어 발전과 줄어드는 요구 자원이 2030년대 초에 만날 것으로 예상한다고 밝혔지만, 상당한 공학적 과제가 남아 있음을 인정했다. PQShield의 창업자 겸 CEO Ali El Kaafarani는 발표문에서 정부와 기업이 "가장 중요한 곳에 즉시 PQC를 도입해야 한다"고 말했다.

주목할 점

핵심 수치는 아직 대규모로 입증되지 않은 매우 긴 비트 플립 시간을 가진 캣 큐비트에 기반하므로, 진정한 시험대는 그 가정을 향한 하드웨어 진전이다. 프리프린트의 동료 평가와 컴파일 선택에 대한 독립적 검증도 지켜볼 만하다. Alice & Bob은 정부와 업계 이해관계자에게 설명하고 있으며, 미국과 영국의 지침이 2035년까지 전환 완료를 목표로 한다는 점을 들어 기관들이 지금 바로 양자내성암호로의 전환을 시작할 것을 촉구했다.