5년, 10년 아니면 더 오래? 양자 컴퓨팅 위협에 대한 타임라인 평가

원문 저자: Justin Thaler(@SuccinctJT), a16z 연구 파트너

원문 번역: AididiaoJP, Foresight News

양자 컴퓨터는 언제 암호를 해독할 수 있을까? 이 타임라인은 종종 과장되어 '긴급하고 포괄적인 포스트-퀀텀 암호학으로의 전환'에 대한 요구를 불러일으킵니다.

그러나 이러한 요구는 종종 조기 이전의 비용과 위험을 간과하며, 다양한 암호학 도구의 위협 본질이 근본적으로 다르다는 점을 무시합니다:

• 포스트-퀀텀 암호화는 즉시 배포되어야 하며, 비용이 아무리 높아도 해야 합니다. 왜냐하면 '지금 훔쳐서 나중에 해독'하는 공격이 이미 존재하기 때문입니다. 오늘 암호화된 민감한 데이터는 수십 년 후에 양자 컴퓨터가 등장하더라도 여전히 엄청난 가치를 지닙니다. 포스트-퀀텀 암호화는 성능 손실과 구현 위험이 있지만, 장기간 비밀로 유지해야 하는 데이터에 대해서는 다른 선택지가 없습니다.
• 포스트-퀀텀 디지털 서명은 별개의 문제입니다. 이들은 위에서 언급한 '저장 후 해독' 공격에 취약하지 않으며, 그 자체의 비용과 위험(크기 증가, 성능 오버헤드, 미성숙한 스킴, 잠재적 취약점)은 즉각적인 행동이 아닌 신중한 계획을 요구합니다.

이 점을 구분하는 것이 매우 중요합니다. 오해는 비용-편익 분석을 왜곡하여 팀이 프로그램 취약점과 같은 더 시급한 보안 위험을 간과하게 만들 수 있습니다.

포스트-퀀텀 암호학으로의 성공적인 전환의 진정한 도전은 행동의 긴급성을 실제 위협과 일치시키는 데 있습니다. 아래에서는 암호화, 서명 및 영지식 증명에 대한 양자 컴퓨팅 위협에 대한 일반적인 오해를 명확히 하고, 특히 블록체인에 대한 의미에 초점을 맞출 것입니다.

타임라인: 암호화 기술을 해독할 수 있는 양자 컴퓨터까지 얼마나 남았나요?

과장된 선전에도 불구하고, 2020년대에 '암호학적으로 관련된 양자 컴퓨터'가 등장할 가능성은 극히 낮습니다.

'암호학적으로 관련된 양자 컴퓨터'란, 내가 의미하는 것은 Shor 알고리즘을 실행할 수 있고, 타원 곡선 암호(예: secp256k1) 또는 RSA(예: RSA-2048)를 합리적인 시간 내에(예: 지속적인 계산이 한 달을 넘지 않음) 공격할 수 있을 만큼 규모가 큰 내결함성, 오류 수정 양자 컴퓨터입니다.

공개된 기술 이정표와 자원 평가에 따르면, 우리는 아직 그러한 컴퓨터로부터 매우 멀리 떨어져 있습니다. 일부 회사들은 2030년 또는 심지어 2035년 이전에 실현 가능하다고 주장하지만, 알려진 진전은 이러한 주장을 뒷받침하지 않습니다.

현재, 트랩 이온, 초전도 큐비트 또는 중성 원자 시스템 등 어떤 양자 컴퓨팅 플랫폼도 RSA-2048 또는 secp256k1을 해독하는 데 필요한 수십만 개에서 수백만 개의 물리적 큐비트(구체적인 수치는 오류율과 오류 수정 스킴에 따라 다름)에 근접하지 못하고 있습니다.

병목 현상은 큐비트 수뿐만 아니라 게이트 충실도, 큐비트 간 연결성, 그리고 깊은 양자 알고리즘을 실행하는 데 필요한 지속적인 오류 수정 회로 깊이에 있습니다. 현재 일부 시스템은 물리적 큐비트 수가 1000개를 초과하지만, 이 숫자만으로는 오해의 소지가 있습니다: 이들은 암호학적 계산에 필요한 연결성과 충실도가 부족합니다.

최근 시스템들은 양자 오류 수정에 필요한 물리적 오류율 문턱에 접근하고 있지만, 지금까지 아무도 몇 개 이상의 논리 큐비트를 안정적으로 실행하지 못했으며, Shor 알고리즘을 실행하는 데 필요한 수천 개의 고충실도, 깊은 회로, 내결함성 논리 큐비트는 말할 것도 없습니다. 개념 증명에서 암호 분석에 필요한 규모를 구현하는 데까지의 격차는 여전히 큽니다.

간단히 말해서: 큐비트 수와 충실도가 여러 수준으로 향상되기 전까지는 암호학적으로 관련된 양자 컴퓨터는 요원합니다.

그러나 기업 보도 자료와 미디어 보도는 종종 혼란을 야기합니다. 주요 혼란점은 다음과 같습니다:

1. '양자 우위' 데모: 현재 데모되는 작업들은 대부분 실제로 유용하지 않도록 설계된 작업들입니다. 단지 기존 하드웨어에서 실행 가능하고 '빠르게 보이기' 때문입니다. 이 점은 선전에서 종종 축소됩니다.
2. '수천 개의 물리적 큐비트' 선전: 이는 일반적으로 공개 키 암호를 공격하는 데 필요한 Shor 알고리즘을 실행할 수 있는 게이트 모델 양자 컴퓨터가 아닌, 양자 어닐링 머신을 가리킵니다.
3. '논리 큐비트'의 오용: 물리적 큐비트에는 노이즈가 있으며, 실용적인 알고리즘은 많은 물리적 큐비트를 통해 오류 수정으로 구성된 '논리 큐비트'를 필요로 합니다. Shor 알고리즘을 실행하려면 수천 개의 이러한 논리 큐비트가 필요하며, 각각은 일반적으로 수백에서 수천 개의 물리적 큐비트가 필요합니다. 그러나 일부 회사들은 과장된 주장을 합니다. 예를 들어, 최근 '거리-2' 오류 수정 코드(오류만 감지 가능, 수정 불가)를 사용하여 논리 큐비트당 단 2개의 물리적 큐비트로 48개의 논리 큐비트를 구현했다고 주장한 사례는 의미가 없습니다.
4. 로드맵의 오도: 많은 로드맵의 '논리 큐비트'는 'Clifford 연산'만 지원합니다. 이러한 연산은 고전 컴퓨터에 의해 효율적으로 시뮬레이션될 수 있으며, 많은 '비-Clifford 게이트'(예: T 게이트)를 필요로 하는 Shor 알고리즘을 실행하기에는 부족합니다. 따라서, 어떤 로드맵이 'X년에 수천 개의 논리 큐비트 달성'을 주장하더라도, 그 회사가 그때쯤이면 고전 암호를 해독할 수 있을 것이라고 예상한다는 의미는 아닙니다.

이러한 관행은 대중(심지어 숙련된 관찰자들 포함)의 양자 컴퓨팅 진전에 대한 인식을 심각하게 왜곡시킵니다.

물론, 진전은 정말로 흥미롭습니다. 예를 들어, Scott Aaronson은 최근 '하드웨어 진전 속도가 놀랍도록 빠르기 때문에' '다음 미국 대통령 선거 전에 Shor 알고리즘을 실행할 수 있는 내결함성 양자 컴퓨터를 보유하는 것이 실제 가능성'이라고 썼습니다. 그러나 그는 이후 이를 암호학적으로 관련된 양자 컴퓨터를 의미하는 것이 아니라고 명확히 했습니다 — 단지 15=3×5를 내결함성으로 분해하는 것(종이와 펜으로 계산하는 것이 더 빠름)조차도 약속을 이행한 것으로 간주합니다. 이것은 여전히 소규모 데모이며, 이러한 실험은 항상 15를 목표로 합니다. 왜냐하면 모듈로 15 연산이 간단하고, 조금 더 큰 숫자(예: 21)는 훨씬 더 어렵기 때문입니다.

핵심 결론: RSA-2048 또는 secp256k1을 해독할 수 있는 암호학적으로 관련된 양자 컴퓨터가 향후 5년 내에 등장할 것이라고 예측하는 것은 — 실제 암호학에 중요합니다 — 공개된 진전에 의해 뒷받침되지 않습니다. 심지어 10년도 여전히 야심찬 목표입니다.

따라서, 진전에 대한 흥분과 '아직도 십여 년은 더 필요하다'는 타임라인 판단은 모순되지 않습니다.

그렇다면, 미국 정부가 2035년을 정부 시스템의 완전한 포스트-퀀텀 이전을 위한 최종 기한으로 정한 것은 어떻습니까? 저는 이것이 대규모 전환을 완료하기 위한 합리적인 시간 계획이라고 생각하지만, 그것이 암호학적으로 관련된 양자 컴퓨터가 그때쯤 나타날 것이라고 예측하는 것은 아닙니다.

'지금 훔쳐서, 나중에 해독' 공격: 누구에게 적용되고 누구에게 적용되지 않나요?

'지금 훔쳐서, 나중에 해독' 공격은 공격자가 지금 암호화된 트래픽을 저장했다가 나중에 암호학적으로 관련된 양자 컴퓨터가 등장하면 해독하는 것을 의미합니다. 국가 수준의 적대자는 이미 미국 정부로부터의 암호화된 통신을 미래 해독을 위해 대량으로 보관하고 있을 가능성이 높습니다.

따라서, 암호화는 즉시 업그레이드되어야 합니다, 적어도 10-50년 이상의 비밀 유지 기간이 필요한 데이터에 대해서는요.

그러나 디지털 서명(모든 블록체인의 기초)은 암호화와 다릅니다: 이는 소급 공격이 필요한 기밀성이 없습니다. 미래에 양자 컴퓨터가 나타나더라도 그때부터 서명을 위조할 수 있을 뿐, 과거 서명을 '해독'할 수는 없습니다. 서명이 양자 컴퓨터가 나타나기 전에 생성되었다는 것을 증명할 수만 있다면, 그것은 위조 불가능합니다.

이것은 포스트-퀀텀 디지털 서명으로의 전환이 암호화 전환만큼 시급하지 않게 만듭니다.

주요 플랫폼들이 정확히 이렇게 하고 있습니다:

• Chrome과 Cloudflare는 이미 웹 TLS 암호화를 위해 하이브리드 X25519+ML-KEM 스킴을 배포했습니다. '하이브리드'는 포스트-퀀텀 안전 스킴(ML-KEM)과 기존 스킴(X25519)을 동시에 사용하여 양쪽의 보안성을 모두 갖추는 것을 의미하며, HNDL 공격으로부터 보호하면서도 포스트-퀀텀 스킴에 문제가 생겼을 때 고전적 보안을 유지합니다.
• Apple의 iMessage(PQ3 프로토콜)와 Signal(PQXDH 및 SPQR 프로토콜)도 유사한 하이브리드 포스트-퀀텀 암호화를 배포했습니다.

이에 비해, 포스트-퀀텀 디지털 서명은 암호학적으로 관련된 양자 컴퓨터가 정말로 임박할 때까지 핵심 네트워크 인프라에 대한 배포가 지연되고 있습니다. 왜냐하면 현재의 포스트-퀀텀 서명 스킴은 성능 저하를 초래하기 때문입니다(아래에서 자세히 설명).

영지식 증명(zkSNARKs)의 처지는 서명과 유사합니다. 비포스트-퀀텀 안전한 zkSNARK들(타원 곡선 암호를 사용하는)조차도 그 '영지식' 속성 자체는 포스트-퀀텀 안전합니다. 이 속성은 증명이 비밀에 관한 어떤 정보도 유출하지 않는다는 것을 보장합니다(양자 컴퓨터도 어쩔 수 없음), 따라서 미래에 해독될 수 있는 '지금 훔칠 수 있는' 기밀성이 없습니다. 따라서, zkSNARKs도 HNDL 공격에 취약하지 않습니다. 양자 컴퓨터가 나타나기 전에 생성된 모든 zkSNARK 증명은 신뢰할 수 있습니다(타원 곡선 암호를 사용하더라도), 양자 컴퓨터가 나타난 후에야 공격자가 가짜 증명을 위조할 수 있습니다.

이것이 블록체인에게 무엇을 의미하나요?

대부분의 블록체인은 HNDL 공격에 취약하지 않습니다.

현재의 비트코인과 이더리움과 같은 비-프라이버시 체인에서, 그들의 비포스트-퀀텀 암호학은 주로 암호화가 아닌 트랜잭션 승인(즉, 디지털 서명)에 사용됩니다. 이러한 서명들은 HNDL 위험을 구성하지 않습니다. 예를 들어, 비트코인 블록체인은 공개되어 있으며, 양자 위협은 이미 공개된 트랜잭션 데이터를 해독하는 것이 아니라 서명 위조(자금 도난)에 있습니다. 이것은 HNDL로부터의 즉각적인 암호학적 긴급성을 제거합니다.

안타깝게도, 심지어 연방준비제도이사회와 같은 권위 있는 기관들의 분석조차도 비트코인이 HNDL 공격에 취약하다고 잘못 주장한 적이 있으며, 이는 전환의 긴급성을 과장했습니다.

물론, 긴급성이 낮아진다고 해서 비트코인이 안전하다는 의미는 아닙니다. 이는 프로토콜 변경에 필요한 거대한 사회적 조정 작업으로부터의 다른 시간적 압력에 직면해 있습니다(아래에서 자세히 설명).

현재의 예외는 프라이버시 체인입니다. 많은 프라이버시 체인들은 수신자와 금액을 암호화하거나 숨깁니다. 이러한 기밀 정보는 지금 훔쳐서 미래에 양자 컴퓨터가 타원 곡선 암호를 해독한 후 소급적으로 비식별화될 수 있습니다. 공격의 심각성은 설계에 따라 다릅니다(예: 모네로의 링 서명과 키 이미지는 트랜잭션 그래프가 완전히 재구성될 수 있게 함). 따라서 사용자가 자신의 트랜잭션이 미래 양자 컴퓨터에 의해 노출되지 않도록 신경 쓴다면, 프라이버시 체인은 가능한 한 빨리 포스트-퀀텀 원시 연산(또는 하이브리드 스킴)으로 전환하거나, 해독 가능한 비밀을 체인에 올리지 않는 아키텍처를 채택해야 합니다.

비트코인의 특별한 난제: 거버넌스 교착 상태와 '잠든 코인'

비트코인의 경우, 양자 기술 자체와는 무관하게 포스트-퀀텀 서명 계획을 시작해야 하는 긴급성을 추동하는 두 가지 현실적인 요소가 있습니다:

• 거버넌스 속도가 느림: 비트코인 변화는 느리며, 어떤 논쟁도 파괴적인 하드 포크를 초래할 수 있습니다.
• 수동적 이전이 불가능함: 코인 소유자는 자신의 코인을 능동적으로 이전해야 합니다. 이는 버려진, 양자에 취약한 코인들이 보호받을 수 없음을 의미합니다. 추정에 따르면, 이러한 '잠들어' 있고 양자에 취약한 BTC는 수백만 개에 달할 수 있으며, 현재 가치는 수천억 달러입니다.

그러나, 양자 위협은 비트코인에게 '하룻밤 사이에' 찾아오는 종말이