1. 비트코인의 정확히 어떤 부분이 양자컴퓨터에 의해 위협받는가?

A) 양자컴퓨터가 실용화되면 못 풀 것이라고, 암호화 되었다고 생각했던 것들이 풀려서 위험성이 커지게 됩니다.

1. 비대칭 키 ECDSA (secp256k1)
   1. 기존의 연산으로는 타원 곡선 이산 로그 문제(elliptic curve discrete logarithm problem, ECDLP) 를 풀기 어렵습니다.
   2. Shor’s Algorithm(쇼어 알고리즘) 에 의해 시간 복잡도를 굉장히 낮추어 풀릴 수 있습니다.
   3. 정확히, 공개키를 통해 비밀키가 역추적이 가능해집니다.
2. 해시 SHA256
   1. 해시 함수 등의 단방향 함수는 비트 섞기, 비선형 연산, 압축 함수 등의 조작을 통해 정보 유실이 발생하기 때문에 역으로(역함수) 돌아가는 것이 불가능합니다.
   2. 따라서, 수치를 대입해가며 답을 찾아야하는데 256비트(2^256) 번을 무작위 대입하는 것은 무지성적입니다.
   3. Grover's algorithm(그로버 알고리즘) 은 복잡도를 2^128 수준으로 낮출 수 있습니다.
   4. PoW 합의(채굴)이나 원천 데이터 가리기(해시) 등에서 위험성이 생길 수 있지만, 이산 로그 파훼 정도의 위험 수준은 아닙니다.

ECDSA (Elliptic Curve Digital Signature Algorithm)

• 이산 로그 문제 (Discrete Logarithm Problem, DLP)

  • 모듈러 연산(mod p) 에서 x 를 찾는 것은 굉장히 어려움.

  $$ y(공개\ 키) = g^{x(비밀\ 키)} \ mod \ p $$

• 타원 곡선 이산 로그 문제 (Elliptic Curve Discrete Logarithm Problem, ECDLP)

SHA-256

• 비트 논리 연산 (AND, XOR, NOT)
• 비트 순환 이동 (Bit Rotation)
• 압축 함수 (Compression Function)