crossroads webzine

비트코인 같은 암호화폐는 타원곡선을 기반으로하는 ECDSA (Elliptic Curve Digital Signature Algorithm) 서명 시스템을 활용하는데, 이를 통해 사용자들의 각 트랜잭션이 인증되고, 자산의 소유권이 증명된다. 이때 ECDSA는 트랜잭션과 소유권의 보안 보장을 위해 1) 개인키를 이용한 서명 생성, 2) 공개키를 이용한 서명 검증, 3) 소유권 증명 기능에 활용된다. 그런데 타원곡선의 암호화 효율성은 ECDSA가 RSA2048 같은 체계보다 양자컴퓨터에 더 취약하게 만드는 요인이 될 수도 있다. ECDSA는 RSA에 비해 상대적으로 복잡도가 작기 때문이다. 이는 ECDSA 서명 체계가 이산 로그 문제(discrete logarithm problem, DLP)에 기반을 두기 때문에 계산 난도는 O(2ⁿ)가 임에 반해, 양자컴퓨터의 쇼어 알고리즘 (Shor’s algorithm)은 이를 효율적으로 다항 시간 이내, 즉, O(n³)로 계산할 수 있기 때문이다. 양자컴퓨터가 어떻게 ECDSA를 깰 수 있다는 것일까? 개인키 d를 이용하여 Q = dG가 존재한다고 생각해 보자. d를 찾기 위해 G와 Q의 선형결합 함수 f(a,b) = aG + bQ의 주기를 찾을 필요가 있다 (a, b는 정수). 이는 f(a,b) = O (항등원)의 관계를 만족하는 최소의 a, b 값을 구하는 것을 의미한다. 어떤 물리적 시스템에서 양자중첩 상태 (예를 들어 n개의 큐비트에 하다마드 게이트를 적용하여 모든 가능한 2ⁿ 상태의 중첩을 생성)가 주어졌다면, 이를 기반으로 쇼어 알고리즘은 모든 유한체 내 값의 조합을 동시에 계산하여 주기를 추출한다. 특히 a, b 값들을 찾기 위해 a와 b를 각각 n비트로 표현하고, 이들의 모든 가능한 조합을 미리 생성된 중첩 상태에 대응시킨 후, 각 조합으로 f(a,b)를 계산하는 ‘양자 게이트’를 설계할 수 있고, 계산 결과는 중첩 상태에 저장한다. 타원곡선이 순환 주기를 갖는다는 사실을 고려한다면 이제 f(a,b) 함수의 주기를 찾는 것이 핵심이다. 이를 위해 중첩 상태에 저장된 f(a,b) 값들에 대해 양자 푸리에 변환(QFT)을 적용하여 가장 큰 가중치를 갖는 주기를 추출할 수 있다. 이를 기반으로 개인키 d가 복구되면 서명도 마음대로 생성할 수 있고, 트랜잭션도 위조할 수 있다. 즉, 비트코인이 보장하던 소유권 증명, 변조 방지, 그리고 익명성이 모두 깨지는 것이다.

물론 이러한 방식은 쇼어 알고리듬이 작동할 수 있는 양자 중첩 상태의 물리적 구현이 필수적이다. 그렇다면 이러한 양자 중첩 상태를 이루기 위한 최소한의 큐비트 규모는 어느 정도일까? 일단 비트코인이 기반을 두고 있는 secp256k1 같은 타원곡선은 256 비트 암호체계이므로, 쇼어 알고리즘에 따라 2*256 = 512개의 논리 큐비트가 필요하다. 그러면 512개의 큐비트만 있으면 되는 것일까? 사실은 그렇지 않다. 왜냐하면 물리적 큐비트의 개수가 논리 큐비트의 개수와 같지 않기 때문이다. 이는 기본적으로 양자 중첩 상태는 노이즈에 매우 취약하기 때문에 생기는 문제다. 양자컴퓨터 커뮤니티에서는 이러한 문제를 해결하기 위해 오류 수정 큐비트를 주기적으로 배열한 격자체를 만드는 방식을 채용했다. 오버헤드는 오류 수정 큐비트와 논리 큐비트가 합쳐진 물리적 큐비트 숫자와 논리 큐비트 숫자의 비율이다. 현재로서는 대략 100-1,000 사이의 값을 보이고 있다. ECDSA 256비트짜리 타원곡선 암호를 다항 시간 이내에 깨려면 논리 큐비트가 512비트 필요한데, 만약 오버헤드가 1,000이라면 실제로 필요한 물리적 큐비트 개수는 512,000개가 되는 셈이다. 구글의 윌로우칩의 경우, 오버헤드를 100 정도까지 낮췄다고 평가되지만, 여전히 이 오버헤드로도 비트코인 암호에 도전하려면 51,200개의 물리적 큐비트가 생성되어야 하고, 쇼어 알고리듬이 작동할 수 있으려면 중첩 상태가 충분히 오랜 시간 (수십-수백 마이크로 초 이상) 유지될 수 있어야 한다. 참고로 윌로우칩에 포함된 물리적 큐비트는 겨우 105개에 불화하다. 오버헤드를 얼마나 낮출 수 있느냐는 물리적 오류율을 얼마나 낮출 수 있느냐로도 결정된다. 물리적 오류율이 1% 수준이면 오버헤드는 1,000 정도, 0.01% 이하까지 낮아지면 10까지도 낮아질 수 있다. 오류율을 낮추기 위해서는 일단 큐비트 배열을 크게 만들어야 한다. 윌로우칩의 경우 2차원 격자 큐비트 배열을 3x3 (17큐비트)에서 7x7 (97큐비트)까지 확장했는데, 이 과정에서 오류율은 2.14배 감소한 것으로 나타났다. 윌로우칩이 채용한 오류 수정 방식인 표면 코드(surface code) 방식은 2차원 격자 큐비트 배열이 커질수록 유리해진다. 왜냐하면 실제 연산을 수행하는 큐비트 사이에 검증자 큐비트를 조밀하게 채워 넣을 수 있기 때문이다. 구글이 계속 scaling law를 따라 몇 년 후 15x15 수준의 2차원 큐비트 배열체를 만들 수 있다면, 물리적 큐비트 숫자는 433에 이르게 되고, 오버헤드가 100 수준이라면 논리 큐비트는 최대 5까지 될 수 있으므로, RSA1024 해독에 근접한다. 25x25 배열체까지 구현하면 물리적 큐비트 숫자는 1,057개에, 논리 큐비트 숫자는 10에 이르러 RSA2048 해독에 근접한다. 구글의 경쟁자인 IBM의 경우, Osprey칩이 433 물리적 큐비트를 가지고 있고, 2025년 1,121 큐비트짜리 Condor가 예정되어 있는데, 이 정도 수준이라면 15년 이내로 50x50 혹은 그 이상의 배열체가 구현될 가능성이 높다. 이러면 RSA4096도 해독할 수 있다.

2차원 물리적 큐비트 격자 배열체 규모 확장과 더불어 오류 수정 성능도 높아지면, 타원곡선 암호 해독은 더 빨리 현실화될 수 있다. 현재는 표면 코드 방식으로 오류를 수정하지만, 앞으로는 LDPC (low-density parity check) 코드 같은 방식이 주가 될 수 있다. 표면 코드 방식은 격자 크기가 커지면 큐비트 오류율이 지수함수적으로 감소한다. 예를 들어 물리적 큐비트 오류율 (P(physical))이 0.01이라면, 5x5 격자에서는 P(logical)~0.000316이고, 7x7 격자에서는 P(logical)~0.0001이 되면서 1/3 이하가 된다. 그렇지만 표면 코드 방식의 단점은 물리적 큐비트 숫자가 격자 규모에 비례하므로 오버헤드 증가를 막기 어렵다는 것이다. 물리적 큐비트 2차원 격자를 100x100으로 구현했다고 가정해 보자. 이 경우 물리적 큐비트 숫자는 10,000개 정도가 된다. 비트코인 ECDSA를 깨기 위해 512비트가 필요하므로, 오버헤드는 10,000/512 ~19, 즉, 20 이하가 되어야 한다. 논리 큐비트 오류율이 10^-15, 오버헤드가 50 정도로 달성된 상황이라면, 100x100 격자에서는 P(physical)이 0.5% 정도로 낮아져야 한다. 즉, 물리적 큐비트 품질의 향상 혹은 더 효율적인 오류 수정 코드가 개발된 후에야 비로소 비트코인 암호체계가 깨질 가능성이 보이는 것이다.

물리적 큐비트 품질 향상이 가능해지려면 결국 현재의 반도체 기술과 소재 기술, 그리고 오류 수정 기술 혁신도 충분히 뒷받침되어야 한다. 현재로서 대량의 큐비트 배열체 구현에서 가장 중요한 기술은 초전도체 기반의 조셉슨 접합 소자다. 초전도 기반 큐비트 외에도 이온트랩(Trapped ion)이나 스핀큐빗(spin qubit)을 이용하는 방식이 있지만, 그나마 현재의 CMOS 공정과 연계되어 집적도 향상을 기대할 수 있는 방식은 스핀큐빗 정도다. 오류 수정 코드 개선을 위해 기대되는 LDPC 코드는 오버헤드도 줄일 수 있고, 큐비트 간 상호작용 (crosstalk)도 줄일 수 있다. 물리적 구현도 어렵지 않으므로, 대규모 큐비트 네트워크에 더 적합할 수 있다. 그래서 LDPC 코드를 이용하면 오버헤드를 10까지 낮출 수도 있다. 그렇지만 단점도 있다. 왜냐하면 실시간 오류 수정 알고리즘이 더 복잡해지기 때문이다. 희망적으로만 본다면 20년 이내로 물리적 큐비트 배열체는 100x100 수준까지, 오버헤드는 50 이하까지, 물리적 큐비트 오류율은 0.05% 이하까지 달성될 수 있을지도 모른다. 이는 논리 큐비트 개수가 500개에 육박하여, RSA2048은 물론 타원곡선 암호 해독도 가시권에 든다는 뜻이다. 그러면 비트코인의 유효기간은 2050년 정도면 끝난다는 것일까?   

물론 암호 시스템 업그레이드가 없으면 그럴 수도 있다. 예를 들어 512비트 논리 큐비트를 달성한 양자컴퓨터는 공개키를 사용하는 트랜잭션부터 바로 공격할 것이다. 아직 사용되지 않은 주소 (비공개키 주소)는 상대적으로 안전하겠지만 공격당하는 것은 시간 문제다. 비트코인 커뮤니티에 대응책이 없는 것은 아니다. 기본적으로 이미 오래전부터 연구되고 있는 ‘양자내성암호’(post-quantum cryptography, PQC) 전환부터 시작할 것이다. 이를 이용하여 소프트포크 혹은 하드포크를 이용하여, 기존의 비트코인 주소를 PQC 주소로 전환하거나, 사용자들이 새로운 키 쌍을 생성하여 잔고를 계속 옮기는 방식을 취할 수도 있다. 물론 PQC의 기술 발전은 결국 하드웨어 문제로 귀결되는데, 현재로서는 양자컴퓨터 물리적 큐비트 스케일링과 오류율 저하 개선 속도가 더 빠르므로 공격 측이 조금 더 진도가 나간 상황으로 볼 수 있다. 비트코인 커뮤니티에게 남은 시간이 20년 정도라고 볼 때, PQC가 정말 현실화될 수 있다면 현재의 암호 체계를 업그레이드하는 방식으로 버틸 수 있을 것이다. 설사 PQC가 현실화되기 어려운 수준이라고 해도, 일단 현재의 256비트 기반 ECDSA를 512비트, 혹은 1,024비트로 순차적으로 업그레이드함으로써 시간을 벌 수는 있다. 양자컴퓨터로 공격측에게 노이즈를 의도적으로 더 많이 부여하여 오버헤드가 다시 늘어나는 효과를 유도할 수도 있다. 이는 논리 큐비트 숫자를 줄이는 역할을 하여 연산의 강력함을 떨어뜨릴 수 있다. 

현재의 양자컴퓨터 기술 발전 속도가 언제까지 scaling law를 따라갈 수 있을지 모를 일이고, 더 중요한 사실은 애초에 양자컴퓨터의 주요 목표는 비트코인 같은 블록체인 깨는 것이 아니기에, 비트코인 같은 블록체인 소유자들은 지금 당장부터 자신의 자산 가치가 0이 될까 걱정에 시달리며 불면증을 겪을 필요는 없을 것이다. 그렇지만 사실 비트코인 같은 타원암호체계는 양자컴퓨터 개발 진영에게는 아주 좋은 연습 문제이자 현실 도전 문제가 되어 줄 수 있으므로, 양자컴퓨터의 위협에 지속적으로 시달리는 것을 근본적으로 막을 수는 없을 것이다. 조금씩 현실로 다가오는 양자컴퓨터 기술 발전으로 인해 인류는 또 전혀 다른 방식과 이론 기반의 암호화 기술 시대로 진입하게 될 것이다. 그 과정에서 인류가 정말 그러한 양자컴퓨터나 암호화 기술을 하드웨어로 구현할 수 있을 정도로 혁신적인 신소재와 미세 공정을 구현할 수 있을지도 관건이지만, 그 역시 강력한 현실 문제가 존재하는 한, 기술 개발 진영들에게는 아주 좋은 동기를 부여하게 될 것이다.