양자내성암호(PQC, Post‑Quantum Cryptography)는 미래의 대형 양자컴퓨터 공격에도 안전하도록 설계된 새로운 공개키 암호 체계를 의미합니다. 오늘날 인터넷 보안을支える RSA, ECC 같은 기존 공개키 암호가 양자컴퓨터 등장 시 근본적으로 깨질 수 있다는 위기 속에서, 이를 대체하기 위해 연구·표준화되고 있는 기술이 바로 양자내성암호입니다.
1. 왜 양자내성암호가 필요한가
현재 우리가 사용하는 공개키 암호(RSA, Diffie‑Hellman, 타원곡선암호 ECC 등)는 “큰 수의 소인수분해”나 “이산 로그 계산”처럼 고전 컴퓨터에겐 풀기 매우 어려운 수학 문제에 기반합니다. 이런 문제는 현존 슈퍼컴퓨터로도 수십억 년이 걸릴 수 있어, 사실상 안전하다고 여겨져 왔습니다.
하지만 1994년 피터 쇼어(Peter Shor)가 발표한 쇼어 알고리즘은, 충분히 큰 규모의 양자컴퓨터가 존재한다면 이 인수분해·이산로그 문제를 다항 시간 안에 효율적으로 풀 수 있음을 보였습니다. 이는 곧 RSA와 ECC가 원리적으로는 양자컴퓨터에 의해 비교적 짧은 시간 안에 해독될 수 있음을 의미합니다. 또한 그로버 알고리즘은 대칭키나 해시 탐색을 제곱근 수준으로 가속시켜, 키 길이와 해시 길이 선택에도 영향을 줍니다.
문제는 “지금 당장”이 아니라 “나중”입니다. 공격자는 오늘 중요 데이터를 가로채어 암호화된 상태로 저장해 두었다가, 수십 년 후 양자컴퓨터가 준비되면 한꺼번에 복호화할 수 있습니다(이른바 Harvest‑now, Decrypt‑later 위협). 국가 기밀, 장기 의료 기록, 금융 데이터, 인프라 제어 정보처럼 장기간 기밀성이 요구되는 정보는 지금 설계되는 시스템부터 양자내성을 고려해야 합니다.
2. 양자내성암호의 기본 개념과 특징
양자내성암호는 말 그대로 “양자 공격에 내성이 있는 암호”를 뜻하며, 양자컴퓨터 위에서 돌아가는 양자암호(양자키분배 QKD 등)와는 다른 개념입니다. 양자내성암호 알고리즘은 모두 기존의 고전 컴퓨터(서버, PC, 모바일, IoT 장비 등)에서 실행되며, 단지 그 수학적 기반이 양자컴퓨터로도 효율적 해결 방법이 알려지지 않은 문제 위에 세워졌다는 점이 핵심입니다.
또한 양자내성암호는 공개키 암호 체계의 대체재라는 점이 중요합니다. 현재 인터넷에서는 TLS, VPN, 전자서명, 블록체인, 소프트웨어 업데이트 인증 등 수많은 프로토콜이 공개키 암호를 이용합니다. PQC는 이 영역에서 RSA/ECC를 교체하거나 함께 사용되도록 설계되어 있으며, 기존 네트워크 인프라와 소프트웨어 스택 위에서 동작한다는 점에서, 별도의 양자 통신 장비를 요구하는 QKD와 구분됩니다.
3. 주요 수학적 기반(알고리즘 패밀리)
양자내성암호는 다양한 수학 구조를 이용해 양자컴퓨터에 강한 문제를 만듭니다. 대표적인 네 가지(또는 다섯 가지) 계열은 다음과 같습니다.
첫째, 격자 기반 암호(Lattice‑based cryptography) 입니다. 고차원 격자에서 “가장 짧은 벡터 찾기(SVP)”나 “오차가 섞인 선형 방정식에서 비밀 벡터 찾기(LWE, Learning With Errors)” 같은 문제가 기반이며, 현재까지 고전·양자 모두에 대해 효율적인 해법이 알려져 있지 않습니다. 격자 기반 암호는 성능과 유연성이 뛰어나 공개키 암호, 키 캡슐화, 전자서명 등 여러 용도로 사용 가능하며, NIST가 선택한 주요 알고리즘 대부분이 이 계열입니다.
둘째, 코드 기반 암호(Code‑based cryptography) 입니다. 오류정정코드의 디코딩 문제, 특히 임의로 섞인 구조 없는 코드의 최소 거리 찾기 문제가 기반입니다. 1970년대 McEliece 암호부터 연구가 이어져 온 전통 있는 분야로, 키 크기가 크다는 단점이 있지만 보안성 측면에서 오랜 검증 역사를 가졌습니다.
셋째, 다변수 다항식 기반 암호(Multivariate cryptography) 입니다. 여러 변수에 대한 다변수 이차식 시스템을 풀어 비밀키를 찾는 문제는 고전·양자 모두에서 매우 어렵다고 여겨지며, 이를 이용한 전자서명 스킴이 오래전부터 제안되어 왔습니다. 다만 구현 복잡도와 일부 제안안의 안전성 이슈로 인해, 표준화에서 선택 받은 후보는 제한적입니다.
넷째, 해시 기반 전자서명(Hash‑based signatures) 입니다. 안전한 암호학적 해시 함수가 유지된다는 가정 하에서, 해시 체인과 머클 트리를 이용해 서명을 구성하는 방식입니다. 이 계열은 해시 함수가 양자 환경에서 Grover 알고리즘으로 인해 효과적인 보안 강도가 절반으로 떨어지더라도, 해시 출력 길이를 늘려 보완할 수 있다는 장점이 있습니다.
마지막으로, 대칭키 기반 강화(Symmetric‑based approach) 도 종종 PQC 논의에 포함됩니다. AES, SHA‑2/3 같은 대칭키·해시 기반 구조는 쇼어 알고리즘의 직접 타깃이 아니기 때문에, 키 길이와 출력 길이를 적절히 늘리면 양자에 대해서도 비교적 안전하다고 평가됩니다. 예를 들어 AES‑128 대신 AES‑256, SHA‑256 대신 SHA‑384/512 등을 사용하는 식입니다. 다만 이것은 공개키 대체가 아니라, 기존 대칭키/해시를 “양자 강건”하게 만드는 보완 조치에 가깝습니다.
4. NIST 표준화와 대표 알고리즘
미국 국립표준기술연구소(NIST)는 2016년부터 전 세계 연구자들을 대상으로 PQC 알고리즘 공모와 검증을 진행해 왔습니다. 수십 개의 후보가 여러 라운드에 걸쳐 공격 분석과 성능 평가를 거쳤고, 2022년 1차 선정과 2024년 공식 표준 발표를 통해 우선 채택 알고리즘을 확정했습니다.
현재 NIST가 발표한 첫 PQC 표준 세트는 다음 세 가지가 핵심입니다.
- ML‑KEM (기존 명칭 CRYSTALS‑Kyber): 키 캡슐화 메커니즘(KEM)으로, TLS 같은 프로토콜에서 RSA/ECDH를 대체해 세션 키를 안전하게 합의하는 용도로 사용됩니다. 격자 기반(LWE 변형)이며 키·암호문 크기와 속도 측면에서 균형이 좋아 “기본 선택”으로 간주됩니다.
- ML‑DSA (CRYSTALS‑Dilithium): 전자서명 알고리즘으로, 코드 서명, 인증서, 블록체인 트랜잭션 서명 등 다양한 영역에서 ECDSA, RSA 서명을 대체하는 핵심 후보입니다. 격자 기반이며 구현이 비교적 단순하고 성능도 우수해 “주력 PQC 서명”으로 추천됩니다.
- SLH‑DSA (SPHINCS+): 해시 기반 전자서명으로, 해시 함수의 보안성에만 의존한다는 점에서 매우 보수적인 선택입니다. 키가 작고 서명 크기가 비교적 큰 편이며, 속도도 느릴 수 있지만, 다른 수학 구조에 대한 신뢰 보완재로 사용됩니다.
추가로 NIST는 FALCON과 HQC를 “추가 표준화 진행 중인 후보”로 두고 있습니다. FALCON은 NTRU 격자 기반 서명으로 서명 크기가 매우 작고 고성능이지만, 부동소수점 연산과 복잡한 샘플링 때문에 구현 난이도가 높습니다. HQC는 코드 기반 KEM으로, 다양한 위협 모델에서의 안정성이 집중 검토되고 있습니다.
NIST는 2024년 FIPS 203, 204, 205를 통해 Kyber(ML‑KEM), Dilithium(ML‑DSA), SPHINCS+(SLH‑DSA)를 공식 연방 표준으로 공표했으며, FALCON에 대한 표준(FIPS 206)도 후속 발표를 예고했습니다. 각국과 산업계는 이 표준을 사실상 글로벌 기준으로 삼아 PQC 전환을 준비하는 상황입니다.