B
Ars Technica 1일 전
양자 컴퓨터, 예상보다 적은 자원으로 암호 해독 가능
중요도
핵심 요약
최근 두 편의 독립적인 연구 논문에 따르면, 비트코인 등에 쓰이는 타원 곡선 암호(ECC)를 해독하는 실용 규모의 양자 컴퓨터 구축에 필요한 자원이 불과 1~2년 전 예상보다 최대 100배나 줄어들었습니다. 중성 원자 기반의 새로운 큐비트 연결 기술과 쇼어 알고리즘의 효율성 개선이 이러한 혁신을 이끌었습니다. 이는 양자 컴퓨팅 기술이 실질적인 암호 해독 수준(CRQC)으로 빠르게 진입하고 있어, 양자 내성 암호(PQC)로의 조속한 전환이 시급해짐을 시사합니다.
번역된 본문
텍스트 설정 스토리 텍스트 크기 작게 표준 크게 너비 * 표준 넓게 링크 표준 주황색 * 구독자 전용 자세히 알아보기 내비게이션으로 최소화
가장 중요한 암호 시스템 중 하나인 타원 곡선(ECC)을 해독할 수 있는 실용 규모의 양자 컴퓨터를 구축하는 데는 불과 1~2년 전만 해도 예상했던 것보다 훨씬 적은 자원만 필요하다는 결론이 두 편의 독자적으로 작성된 백서를 통해 나왔다.
한 논문에서 연구진은 서로 자유롭게 접근할 수 있는 재구성 가능한 큐비트로 중성 원자를 사용하는 방법을 시연했다. 그들은 이러한 접근 방식을 통해 양자 컴퓨터가 이전 추정치보다 100배 적은 오버헤드를 사용하면서 10일 안에 256비트 타원 곡선 암호(ECC)를 해독할 수 있음을 보여주었다.
두 번째 논문에서는 구글 연구진이 비트코인 및 기타 암호화폐의 ECC 보호 블록체인을 9분 이내에 해킹하는 동시에 자원을 20분의 1 수준으로 줄이는 방법을 시연했다.
종합해 볼 때, 이 두 논문은 실용 규모의 암호학적으로 관련된 양자 컴퓨팅(CRQC)이 의미 있는 진전을 보이고 있다는 최신 신호다. 이러한 발전은 주로 물리학자와 컴퓨터 과학자들이 개발한 새로운 양자 아키텍처에 의해 주도되고 있다. 이들은 큐비트(고전 컴퓨팅 비트의 양자 아날로그)가 환경과 상호작용할 때 발생하는 오류가 있더라도 올바르게 작동하는 양자 컴퓨터를 만들기 위해 노력하고 있다.
또 다른 핵심 동력은 1994년에 발표된 쇼어(Shor) 알고리즘의 성능을 높이는 점점 더 효율적인 알고리즘이다. 쇼어 알고리즘은 양자 컴퓨팅이 오늘날 고전 컴퓨터의 지수 시간보다 훨씬 빠른 다항식 시간(특히 세제곱 시간)으로 ECC 및 RSA 암호 시스템을 해독할 수 있음을 증명한 일련의 수식이다.
두 논문 모두 아직 동료 평가를 거치지 않았다.
2015년부터 2022년까지 마이크로소프트의 양자 내성(Post-quantum) 전환을 감독했고 현재 파케스터 컨설팅 그룹(Farcaster Consulting Group)에서 근무하는 암호학 엔지니어 브라이언 라마키아(Brian LaMacchia)는 다음과 같이 말했다. "연구 커뮤니티는 효율적이고 실용적인 CRQC를 실현하는 데 필요한 물리적 큐비트와 양자 알고리즘 모두에서 꾸준한 진전을 이루고 있습니다. 두 논문 모두 실용적인 CRQC를 갖게 될 시기에 대한 새로운 확정적인 날짜를 제시한다고 생각하지 않습니다(물론 우리는 그런 적이 없었습니다). 하지만 두 논문 모두 우리가 실현 가능한 CRQC를 향한 길을 계속 걷고 있으며, 그 목표를 향한 진전이 느려지지 않고 있다는 증거를 제공합니다."
'광 집게'에 원자 가두기
가장 많은 주목을 받고 있는 논문은 ECC를 깨는 데 필요한 물리적 큐비트 수를 100분의 1로 줄일 수 있는 내결함성 양자 컴퓨팅(FTQC)을 만드는 비교적 새로운 접근 방식을 취하고 있다. 초전도 기반의 보다 일반적인 접근 방식과 달리, 연구진은 중성 원자를 사용하여 물리적 큐비트를 구축했다. 레이저를 사용하여 원자를 냉각시키는 이 공정은 개별 원자를 '광 집계(Optical tweezers)'라고 알려진 조밀하게 집중된 빛의 묶음 안에 가둔다. 각 광 집게는 단일 원자를 잡아낸다. 연구진은 광 다중화(Optical multiplexing)를 사용하여 이렇게 갇힌 원자의 대규모 어레이를 만들 수 있다.
이 접근 방식의 장점은 모든 물리적 큐비트가 다른 모든 물리적 큐비트와 상호작용할 수 있다는 것이다. 이러한 '비국지적(Non-local)' 통신은 큐비트가 2D 그리드에 배치되고 바로 인접한 4개의 큐비트와만 상호작용할 수 있는 초전도 방식의 큐비트 상호작용과는 큰 차이가 있다. 큐비트가 멀리 떨어진 큐비트와 상호작용할 수 있는 능력은 오류 수정을 훨씬 더 효율적으로 만든다. 비국지적 통신을 통해 결함 검사의 수와 철저성을 획기적으로 높일 수 있기 때문이다.
결과적으로 '단 10,000개의 재구성 가능한 원자 큐비트로도 쇼어 알고리즘이 가능하다'라는 제목의 연구진 논문에 따르면, 양자 컴퓨터는 10일 안에 ECC-256을 해독하는 데 30,000개 미만의 물리적 큐비트만 필요하며, 이는 이전 추정치보다 몇 자릿수 더 효율적인 수치다. 작년에 별도의 연구팀은 6,000개 이상의 큐비트를 초과하는 중성 원자 트래핑 어레이를 구축할 수 있음을 보여주었다. 고품위도(High fidelity)를 가진 대규모 양자 연산의 발전과 결합할 경우, 중성 원자는 실행할 잠재력을 가지고 있다.
원문 보기 (영어)
Text settings Story text Size Small Standard Large Width * Standard Wide Links Standard Orange * Subscribers only Learn more Minimize to nav Building a utility-scale quantum computer that can crack one of the most vital cryptosystems—elliptic curves—doesn’t require nearly the resources anticipated just a year or two ago, two independently written whitepapers have concluded. In one, researchers demonstrated the use of neutral atoms as reconfigurable qubits that have free access to each other. They went on to show this approach could allow a quantum computer to break 256-bit elliptic-curve cryptography (ECC) in 10 days while using 100 times less overhead than previously estimated. In a second paper, Google researchers demonstrated how to break ECC-securing blockchains for bitcoin and other cryptocurrencies in less than nine minutes while achieving a 20-fold resource reduction. Taken together, the papers are the latest sign that cryptographically relevant quantum computing (CRQC) at utility-scale is making meaningful progress. The advances are largely being driven by new quantum architectures developed by physicists and computer scientists in a push to create quantum computers that operate correctly even in the presence of errors that occur whenever qubits—the quantum analog to classical computing bits—interact with their environment. The other key drivers are ever-more efficient algorithms to supercharge Shor’s algorithm, the 1994 series of equations proving that quantum computing could break the ECC and RSA cryptosystems in polynomial time, specifically cubic time , far faster than the exponential time provided by today’s classical computers. Neither paper has been peer-reviewed. “The research community continues to make steady progress on both the physical qubits and the quantum algorithms necessary to realize an efficient and practical CRQC,” said Brian LaMacchia, a cryptography engineer who oversaw Microsoft’s post-quantum transition from 2015 to 2022 and now works at Farcaster Consulting Group. “I don’t think either paper gives us a new, hard date for when we’re going to have a practical CRQC (which of course we’ve never had), but they both provide evidence that we are continuing to march down the road to a realizable CRQC and progress toward that goal is not slowing down.” Trapping atoms in “optical tweezers” The paper that is getting the most attention takes a relatively new approach to creating fault-tolerant quantum computing (FTQC) that can reduce the number of physical qubits required to break ECC by a factor of 100. Unlike more common approaches based on superconducting, the researchers built physical qubits out of neutral atoms. Using lasers to cool atoms, the process traps individual atoms into tightly focused beams of light known as “optical tweezers.” Each tweezer snags a single atom. Using optical multiplexing, the researchers can make large arrays of these trapped atoms. The benefit of this approach is that all physical qubits can interact with all other physical qubits. These “non-local” communications are a major departure from qubit interaction in superconducting approaches, where qubits are laid out on a 2D grid and can interact with only their four immediately adjacent qubit neighbors. The ability for qubits to interact with very far-away qubits makes error correction significantly more efficient, since non-local communication allows for drastically increasing the number and thoroughness of fault checks. As a result, the researchers’ paper—titled Shor’s algorithm is possible with as few as 10,000 reconfigurable atomic qubits —says a quantum computer needs fewer than 30,000 physical cubits to break ECC-256 in 10 days, orders of magnitude more efficient than previous estimates. A separate research team last year showed that they could build neutral atom trapping arrays exceeding 6,000 qubits. Combined with advances in large-scale quantum operations with high fidelity, neutral atoms have the potential to run fault-tolerant quantum computing. “While substantial work is needed to integrate these advances into a complete apparatus and scale system sizes to the required levels, our analysis indicates that appropriately designed neutral-atom architectures could support cryptographically relevant implementations of Shor’s algorithm,” the researchers wrote. “This finding underscores the importance of ongoing efforts to transition widely deployed cryptographic systems to post-quantum standards designed to be secure against quantum attacks.” Google is looking out for the crypto bros A separate paper released by Google researchers also shows progress in using Shor’s algorithm to break ECC-256, specifically over secp256k1, the elliptic curve that forms the backbone of bitcoin and other blockchain cryptography. The researchers said they have devised improvements to Shor’s algorithm that make it possible to crack the public key in a bitcoin address in under 10 minutes with resources that are 20 times smaller than those achieved in 2003 research . Specifically, Google said it has compiled two quantum circuits that solve the elliptic-curve discrete logarithm problem. One requires fewer than 1,200 logical qubits and 90 million Toffoli gates, and the other needs fewer than 1,450 logical qubits and 70 million Toffoli gates. A logical qubit is a fault-tolerant qubit that’s encoded using hundreds (or thousands) of physical qubits. The researchers estimate their machine needs roughly 500,000 physical qubits, half of what the same team estimated last June was needed to break 2048-bit RSA, which has a much larger key size. A Toffoli gate is a resource-intensive operation that’s a key driver in the amount of time required to complete an algorithm. In a move that’s turning heads in security circles, Google isn’t releasing the algorithmic improvements that make this achievement possible. Instead, the researchers released a zero-knowledge proof that mathematically proves the existence of the algorithmic enhancement without disclosing it. “The escalating risk that detailed cryptanalytic blueprints could be weaponized by adversarial actors necessitates a shift in disclosure practices,” the authors explained. “Accordingly, we believe it is now a matter of public responsibility to share refined resource estimates while withholding the precise mechanics of the underlying attacks.” The researchers, who said they consulted with the US government in forging the new policy, went on to say that “progress in quantum computing has reached the stage where it is prudent to stop publishing details of improved quantum cryptanalysis to avoid misuse.” The move, recently proposed by influential researcher Scott Aaronson , is a complete turnaround from the strict 90-day disclosure policies Google’s Project Zero pioneered two decades ago and an accepted norm that has driven security research for even longer. Other researchers are already criticizing the lack of details. “I think it’s alarmist to claim an immediate security risk from an algorithm that requires a computer that doesn’t exist,” Matt Green, a professor at Johns Hopkins University who studies cryptography, said. “Given that the stakes here are so low (for the same reason) I’d classify it as less harmful, and more on the hype side. I think it’s more of a PR trick than a serious concern anyone has.” Google is also facing scrutiny for focusing on the harm CRQC poses to cryptocurrencies—an obsession of vocal influencers and the current White House—rather than on TLS implementations, DocuSign signatures, digital certificates, or any other number of more general applications that affect larger populations of people. “While CRQCs certainly do pose a threat to blockchain-based technologies based on classical ECC algorithms, they are just one of many systems in our modern world that need to transition quickly to PQC,” LaMacchia said, referring to post-quantum cryptography. “Especially when reading some of the policy proposals