양자 컴퓨터가 비트코인에 미칠 영향
양자 컴퓨터(Quantum Computer)를 쉽게 소개하고 이것이 비트코인 암호 체계에 미칠 영향을 서술합니다.
[목 차]
- 양자 컴퓨터란
- 양자 컴퓨터의 비트코인 공개키 암호 체계 무력화
- 비트코인 암호 체계의 임계점
양자 컴퓨터란
양자 컴퓨터(Quantum Computer)는 중첩, 얽힘, 확률 진폭과 같은 양자 물리학의 고유한 동작을 컴퓨팅에 적용하는 컴퓨터입니다. 기존 디지털 컴퓨터에서 기본 정보 단위로 비트(bit)를 사용하는 것과 달리, 양자 컴퓨터는 기본 정보 단위로 큐빗(Qubit, Quantum bit)을 사용합니다.
[중첩(Superpostition)]
0 또는 1로만 존재할 수 있는 디지털 컴퓨터의 이진 비트와 달리 큐빗은 가능한 모든 상태를 중첩시켜 보유할 수 있습니다.
큐빗은 관찰하지 않으면 중첩된 상태로 존재하고, 관찰하면 상태들 중 하나로 나타납니다.
각 상태는 확률로 존재합니다. 관찰하면 각 확률만큼 결과를 확인할 수 있습니다. 예를 들어 상태 8의 확률이 90%라면 90%의 확률로 8을 관찰할 수 있습니다.
[얽힘(Entanglement)]
큐빗들은 서로 짝을 이뤄 얽혀있을 수 있습니다. 한쪽의 상태와 다른 쪽의 상태가 얽혀서 존재합니다. 아래 그림처럼 한쪽을 관찰하여 상태 4를 얻어내면 그 상태와 얽혀있던 다른 쪽 상태 8도 나타납니다.
[확률진폭(Probability Amplitude)]
큐빗의 확률은 확률진폭의 절댓값 제곱입니다. 따라서 하나의 확률을 두 개의 다른 확률진폭으로 표현할 수 있습니다. 확률진폭은 아래와 같이 복소수 a±bi로 표현합니다.
[양자 알고리즘(Quantum Algorithm)]
양자 알고리즘은 디지털 컴퓨터의 알고리즘과 차이가 있습니다. 큐빗은 가능한 모든 상태를 중첩시켜 가지고 있기 때문에 큐빗에 대해 작업한다는 것은 곧 모든 상태를 한번에 작업하는 것을 의미합니다. 가령 ‘0, 1, 2, 3’을 중첩하여 가지고 있는 큐빗에 ‘+1’ 연산을 1회 수행하면 ‘0+1, 1+1, 2+1, 3+1’로 네 상태 모두에 ‘+1’ 연산이 적용됩니다.
큐빗에 대한 작업은 레이저를 이용해 이루어집니다. 따라서 큐빗에 대한 작업은 “레이저를 쏜다”라는 표현으로 대체하겠습니다.
양자 컴퓨터가 내놓는 답은 확률적으로 결정되기 때문에 실제 가장 높은 확률을 갖는 답을 찾기 위해선 레이저를 쏘는 작업을 여러번 반복해야 합니다. 이를 통해 우리가 찾는 답이 매우 높은 확률을 갖도록 유도할 수 있습니다.
양자 컴퓨터의 비트코인 공개키 암호 체계 무력화
양자 컴퓨터는 현대에 가장 널리 쓰이고 있는 공개키 암호 체계를 무력화할 수 있습니다. 공개키 암호는 이산 로그 문제 해결에 오랜 시간이 걸린다는 점을 이용한 암호 체계입니다. 그런데 쇼어의 알고리즘은 양자 컴퓨터로 이산 로그 문제를 짧은 시간 내에 수행할 수 있음을 보였습니다.
[이산 로그 문제]
이산 로그(DL, Discrete Logarithms)란 1 보다 큰 자연수 a와 정수 b에 대하여 a^x = b 를 만족하는 정수 x 입니다. 이산 로그 문제(DLP, Discrete Logarithm Problem)란 이산 로그 x 를 찾는 문제를 뜻합니다.
알려져 있는 이산 로그 문제 해결 알고리즘은 전수 조사, Baby-step Giant-step Algorithm (아기걸음 거인걸음) 등 여러 가지가 있지만 아직까지 효율적이라 평가 받는 알고리즘은 만들어지지 않았습니다. 여기서 효율적이라는 말은 디지털 컴퓨터로 다항 시간(polynomial time) 내에 계산이 가능함을 뜻합니다.
이산 로그 문제는 불가역성을 지닙니다. 한 방향으로의 계산은 쉬우나 반대 방향으로의 계산은 불가능하다는 뜻입니다. 불가역성을 가지는 함수들은 ‘트랩 도어(trapdoor)’ 함수라고 불리며 현대 암호학에 사용되고 있습니다.
[비트코인 공개키 암호 체계]
비트코인은 UTXO 접근 권한을 부여하는 한 쌍의 키를 생성할 때에 이 공개키 암호 체계를 사용하고 있습니다.
비트코인은 알려진 이산 로그 트랩 도어 함수 중 타원곡선 곱셈 함수를 사용합니다. 이 함수를 이용한 알고리즘을 타원곡선 디지털서명 알고리즘(ECDSA, Elliptic Curve Digital Signature Algorithm)이라고 부릅니다. ECDSA의 이산 로그 문제는 유한체 타원곡선 곱셈 함수 상에서 정의한 곱셈의 역연산을 의미하고 ECDLP(Elliptic Curve Discrete Logarithm Problem)라 부릅니다.
현재 디지털 컴퓨터로 ECDLP를 수행하려면 지수 시간(exponential time)이 필요합니다. 현실적인 시간 내에 수행할 수 없는 수준입니다.
[쇼어의 알고리즘(Shor’s Algorithm)]
1994년 Peter Shor는 양자 컴퓨터를 이용하면 이산 로그 문제인 인수 분해를 다항 시간에 할 수 있음을 보였습니다. 이 알고리즘을 이용하면 ECDLP도 다항 시간에 풀 수 있습니다.
자연수를 인수 분해하는 과정은 다음과 같습니다. 인수 분해하려는 자연수를 N, N 보다 작은 임의의 자연수를 r 이라 합니다. 그리고 아래와 같은 숫자열을 만듭니다.
이 숫자열은 p 를 주기로 반복됩니다. N 과 r^(p/2)+1 의 최대공약수와 N 과 r^(p/2)-1 의 최대공약수는 높은 확률로 N의 인수가 됩니다.
이를 양자 컴퓨터에서는 다음과 같이 계산합니다.
각각 m 개의 큐빗으로 이루어진 입력 큐빗과 결과 큐빗이 있습니다. 각 큐빗은 0 과 1 이 중첩되어 있습니다. 입력 큐빗과 결과 큐빗은 얽혀있습니다. 결과 큐빗이 나타내는 수를 i 라고 하면 i 는 0 에서 2^m-1 까지의 자연수입니다.
결과 큐빗에 r^i mod N 을 계산하는 레이저를 쏘면 r¹ mod N, r² mod N, …, r^(2^(m-1)) mod N 이 한번에 계산되어 중첩됩니다.
결과 큐빗을 관찰하면 입력 큐빗에는 해당 결과를 출력하는 숫자들만이 남아있는 상태로 변화합니다. 이 숫자들 간의 차이가 곧 숫자열의 주기 p 가 됩니다.
디지털 컴퓨터로 숫자열에 대한 계산을 하려면 2^m 번 계산을 수행해야 하지만 양자 컴퓨터로는 한번에 이 계산을 할 수 있습니다. 이외의 연산들까지 모두 고려하였을 때 쇼어의 알고리즘은 결국 다항 시간에 인수 분해를 수행할 수 있습니다.
[양자 컴퓨터의 비트코인 공개키 암호 체계 무력화]
쇼어의 알고리즘을 실행할 수 있다면 비트코인에서 사용하는 ECDSA 암호 체계를 비롯한 많은 암호 체계들은 깨질 것입니다. 이제 논의는 ‘쇼어의 알고리즘을 실행할 수 있는지’로 넘어가게 됩니다.
비트코인 암호 체계의 임계점
지금의 기술로는 쇼어의 알고리즘을 실행할 수 없습니다. 양자 컴퓨터는 그 성능이 어느 정도 되어야 쇼어의 알고리즘을 실행하여 비트코인의 암호 체계를 위협할 것인지 다음 소개할 논문이 보여줍니다.
Holmes et al.은 Assessment of Quantum Threat To Bitcoin and Derived Cryptocurrencies(2021, iacr) 논문에서 양자 컴퓨터가 비트코인을 어떻게 위협할 것인지 분석하였습니다.
[양자 컴퓨터가 비트코인을 공격하는 방법]
비트코인에서 거래(Transaction)는 생성 후 네트워크에 전파되고 합의를 통해 블록에 포함되어 그 무결성이 증명됩니다. 이때 ECDSA로 생성된 공개키는 거래에 포함되어 네트워크에 함께 전파됩니다.
비트코인의 블록 생성 시간(Block Interval Time)은 약 10분으로, 10분 동안 공개키는 누구나 볼 수 있는 상태가 됩니다. 공개키에 대응하는 개인키를 가진 사람은 해당하는 화폐를 사용할 수 있습니다. 현재 디지털 컴퓨터로는 10분 내에 ECDSA 공개키로부터 개인키를 계산해낼 수 없습니다.
그러나 양자 컴퓨터가 10분 내로 ECDSA 개인키 계산을 수행해내면 화폐를 가로챌 수 있습니다.
[비트코인 암호 체계의 임계점은 언제 오는가]
따라서 양자 컴퓨터가 10분 내에 ECDSA 개인키를 계산할 수 있게 되는 시점이 비트코인 암호 체계의 임계점이라고 볼 수 있습니다.
Number of Qubits — Proos and Zalka는 256-bit 개인키를 사용하는 ECDSA 알고리즘을 풀기 위해서 1536개의 큐빗이 필요하다고 분석했습니다. Roetteler et al.은 2330개의 큐빗이, Haner et al.은 2338에서 2124 개의 큐빗이 필요하다고 분석했습니다.
Clock Speed — 처리되지 않은 거래가 존재하는 시간(Unprocessed Transaction Time), 즉 블록 생성 시간이 짧아질수록 양자 컴퓨터의 클럭 속도(clock speed)는 아래 그래프와 같이 빠르게 증가해야 합니다.
Noise and Error Rates —양자 컴퓨터의 큐빗에는 에러가 발생하기 쉽습니다. Cross et al.은 요구되는 에러율을 아래와 같이 분석하였습니다.
현재 에러율은 양자 컴퓨터가 안고 있는 가장 주요한 문제입니다. Riggetti Computing의 창립자 Chad Riggetti는 “It is really the difference between a $100 million, 10,000-qubit quantum computer being a random noise generator or the most powerful computer in the world” 라고 말하며 에러율 연구의 필요성을 역설하기도 했습니다.
[공격을 막으려면]
여러 가지 예방법이 있을 수 있습니다.
첫째, ECDSA와 같이 양자 컴퓨터에 취약한 암호가 아닌 양자 내성이 있는(Quantum-resistant) 암호 체계로 변경하면 됩니다. 그러나 이처럼 보안 장치를 더하는 방법은 화폐의 사용성을 저해할 수 있으므로 주의가 필요합니다.
둘째, 사용자가 행동을 바꾸면 됩니다. ECDSA 키 쌍을 재사용하지 않고 다중 서명(multi-signature)을 사용하는 것은 양자 컴퓨터 공격을 막는 효과가 있습니다. 양자 컴퓨터의 공격 실행에도 비용이 발생하므로 높은 금액을 송금할 때에는 높은 수수료를 붙이는 것도 방법이 될 수 있습니다.
마지막으로 블록 생성 시간을 줄이는 방법이 있습니다. 양자 컴퓨터 공격은 블록 생성 시간이 상대적으로 긴 작업 증명(PoW, Proof-of-Work)에 유효합니다. 따라서 블록 생성 시간을 줄이거나 블록 생성 시간이 짧은 합의 알고리즘으로 변경하여 공격을 막을 수 있습니다.
[지금 무얼 해야 하는가]
최근 구글에서 양자 우위(Quantum supremacy)를 달성했다고 발표한 양자 컴퓨터는 53개의 큐빗을 사용했습니다. D-WAVE 사는 1000개 이상의 큐빗을 사용한 양자 컴퓨터를 발표했지만 그 성능에는 논란이 있습니다.
이더리움 창시자 비탈릭 부테린은 “양자 컴퓨터에 대한 내 생각은 수소 폭탄과 핵융합 발전만큼 동떨어져 있다는 것”, “양자 우위 검증과 양자 컴퓨터의 실용화는 거리가 먼 얘기”라고 말하며 양자 컴퓨터에 대한 걱정은 시기상조라는 의견을 보였습니다.
그러나 논문은 양자 컴퓨터 기술이 지수적(Exponential)으로 발전하고 있다고 분석했습니다. 따라서 암호 기술에 의존하는 블록체인에서도 서서히 논의가 필요하지 않을까 생각합니다.
맺는 말
지금까지 양자 컴퓨터가 비트코인을 위협할 수 있다는 내용을 살펴 보았습니다.
서울대학교 컴퓨터공학과 이광근 교수는 현재 양자 컴퓨터의 발전 단계는 디지털 컴퓨터의 1930년대 모습과 같다며 양자 컴퓨터에 대해 밝게 전망했습니다. Post-quantum cryptography 라는 연구자 그룹 또한 아래와 같이 말하며 양자 컴퓨터에 대한 기대감을 내비쳤습니다.
“Imagine that it’s fifteen years from now. Somebody announces that he’s built a large quantum computer. RSA is dead. DSA is dead. Elliptic curves, hyperelliptic curves, class groups, whatever, dead, dead, dead. So users are going to run around screaming and say ‘Oh my God, what do we do?’ Well, we still have secret-key cryptography, and we still have some public-key systems. There’s hash trees. There’s NTRU. There’s McEliece. There’s multivariate-quadratic systems. But we need more experience with these. We need algorithms. We need paddings, like OAEP. We need protocols. We need software, working software for these systems. We need speedups. We need to know what kind of key sizes to use. So come to PQCrypto and figure these things out before somebody builds a quantum computer.” — Post-quantum cryptography
그러나 한편으로는 양자 컴퓨터에 대한 회의론도 존재합니다. 일례로 수학자 질 칼라이는 “양자 컴퓨터, 기적인가 신기루인가?”라며 양자 컴퓨터는 결국 동작하지 않을 것이라고 주장하였습니다.
양자 컴퓨터는 기적일지 신기루일지 우리도 지켜볼 필요가 있어 보입니다.
[참고]
글쓴이: 이준하
