양자 후 암호(Post-Quantum Cryptography, PQC)는 양자 컴퓨터를 이용한 공격에 대해 다항 시간 내에 해독되지 않을 것으로 기대되는 암호 체계를 총칭하는 용어이다. 의역하여 양자내성암호(Quantum-Resistant Cryptography) 또는 양자안전암호(Quantum-Safe Cryptography)라고도 한다.
기존의 공개키 암호(RSA, ECC 등)는 소인수분해, 이산로그, 타원곡선 이산로그 문제 등 세 가지 수학적 난제 중 하나에 기반하여 설계되었는데, 이들은 피터 쇼어(Peter Shor)가 1994년에 발표한 쇼어 알고리즘(Shor's algorithm)에 의해 양자 컴퓨터에서 효율적으로 해독될 수 있음이 이론적으로 증명되었다. 양자 후 암호는 이러한 취약성에 대응하여, 양자 컴퓨터로도 효율적으로 해결하기 어려운 다른 수학적 난제들을 기반으로 설계된 차세대 암호 기술이다.
양자컴퓨팅 환경에 적합한 통신 기술로는 양자 후 암호(PQC)와 양자 키 분배(Quantum Key Distribution, QKD)가 있다. 영국 국가사이버보안센터(NCSC)는 모든 정부 기관과 군사 분야에서 QKD 사용을 보증하지 않으며, 양자컴퓨터 위협의 최적 대안은 PQC라고 발표한 바 있다.
현재 양자 후 암호 연구는 다음과 같은 여섯 가지 접근 방식으로 진행되고 있다.
격자 기반 암호(Lattice-based Cryptography) Learning with Errors(LWE), Ring-LWE 등의 문제를 기반으로 하는 암호 알고리즘이다. CRYSTALS-KYBER(키 교환/공개키 암호)와 CRYSTALS-DILITHIUM, FALCON(전자서명) 등이 대표적이며, NIST 표준화 공모에서 최종 선정되었다.
다변수 다항식 기반 암호(Multivariate Cryptography) 유한체 상에서 다변수 다항식의 해를 구하는 문제의 어려움에 기반한다. Rainbow(Unbalanced Oil and Vinegar) 전자서명이 대표적이다.
해시 기반 암호(Hash-based Cryptography) 일회용 서명(Lamport 서명)과 Merkle 서명 알고리즘, XMSS, SPHINCS, WOTS 등이 이에 속한다. 서명 가능 횟수가 제한된다는 특징이 있다.
부호(코드) 기반 암호(Code-based Cryptography) 오류 정정 부호의 복호 문제에 기반한다. McEliece 암호 알고리즘이 40년 이상 안전성이 유지된 대표적 사례이며, NIST 표준화에서 Classic McEliece가 최종 후보로 선정되었다.
초특이 타원곡선 아이소제니 암호(Isogeny-based Cryptography) 초특이 타원 곡선 간의 아이소제니(Isogeny)를 구성하는 문제의 어려움에 기반한다. 기존 Diffie-Hellman 키 교환과 유사하게 작동하며 순방향 비밀성을 제공한다.
대칭키 암호의 양자 내성 Grover의 알고리즘으로 인해 대칭키 암호의 탐색 속도가 향상되지만, 키 크기를 두 배로 늘리면 효과적으로 대응 가능하다. AES 등 기존 대칭키 암호는 충분히 큰 키를 사용할 경우 양자 컴퓨터 공격에 대해 상대적으로 안전한 것으로 간주된다.
미국 국립표준기술연구소(NIST)는 2016년부터 양자 후 암호 표준화 공모전을 진행하였으며, 2024년 8월 CRYSTALS-KYBER(공개키 암호/키 교환), CRYSTALS-DILITHIUM(전자서명), FALCON(전자서명), SPHINCS+(전자서명)를 최종 표준 알고리즘으로 선정하여 발표하였다. 이는 기존 RSA 및 타원곡선 암호를 점진적으로 대체하기 위한 국제적 표준화 노력의 일환이다.
