Post Quantum Cryptography(PQC)

Post-Quantum Cryptography(PQC)

지금까지의 전통적인 디지털 컴퓨터는 데이터를 0, 1의 binary 형태로 표현하여 연산을 수행하는 구조이다. Quantum computer는 양자역학을 이용하는 방식이다. 어떤 상태가 0이면서 1인 중첩된 상태를 가질 수 있다. 따라서 0, 1을 이분법적으로 나누지 않고 동시에 두 가지 연산을 하는 것처럼 동작할 수 있다. 이전에는 이론적으로만 논의가 되었는데 최근에는 실제 컴퓨터가 구현이 되어서 구체적으로 논의되고 있다. 아직 범용으로 가기에는 갈길이 굉장히 멀고, 아주 제한된 문제에서만 활용가능하다는 한계가 있지만 양자컴퓨터의 발전은 진전이 있다.

nature에서 2019년 10월 23일, 전통적인 슈퍼컴퓨터를 이용해서 풀기 어려운 문제를 Google에서 만든 양자역학을 이용한 컴퓨터인 Google Quantum Supremacy 로 풀수 있다는 내용의 논문이 개제되었다. 실용성을 논하기에는 이른감이 있다. 실제 양자 컴퓨터가 현실적인 문제를 해결한 사례라는 점에 의미가 있다.
Quantum supremacy using a programmable superconducting processor

또한 IBM에서는 Quantum Computer의 computing power를 cloud에 올려두고 일반 사용자들이 활용할 수 있도록 하는 IBM Quantum Experience 서비스를 제공한다.
IBM Quantum Experience

Quantum Computer 가 등장하면서 기존의 전통적인 컴퓨터가 성능상의 이유로 해결하지 못한 문제를 풀 수 있는 분야가 생겨나고 있다. 그중에 가장 대표적인 분야가 암호분야 이다. 공개키 암호를 설계할 때 수학적으로 풀기 어려운 문제 에 기반하여 암호 알고리즘을 설계했다. 이때 수학적으로 풀기 어려운 문제는 대표적으로 RSA처럼 정수의 소인수 분해 문제 와 Deffie-Helman이나 Ellgamal처럼 Discrete Logarithm 문제 에 근거한 문제이다. Elliptic curve는 조금 차이가 있지만 근본적으로는 Discrete Log를 이용한 방식으로 볼 수 있다.

NIST PQC Standardization

이미 Quantum computer를 이용하여 RSA나 DH를 공격하는 방법은 20년전에 소개가 되기 시작했고, 최근 양자컴퓨터의 등장이 가시화되면서 새로운 암호 알고리즘의 필요성이 대두되었다. 이에 NIST에서는 2016년을 시작으로 Quantum computer가 등장에 따른 향후 암호 알고리즘의 방향성과 해결책을 제시하기 위한 움직임을 시작했다. NIST가 PQC에 대응하여 준비하는 암호 기능은 PKE(Public-Key Encryption), KEM(Key Encapsulation Mechanism), Digital Signatures의 계열이 있다. 자세한 내용은 NIST PQC Standardization에서 얻을 수 있다.