양자 위협과 격자 기반 암호

양자 위협 모델

현대 공개키 암호(PKI)는 주로 소인수 분해(RSA)와 이산 로그 문제(ECC)의 어려운 난제에 의존한다. 쇼어 알고리즘(Shor’s algorithm)은 양자 컴퓨터를 사용하여 다항 시간 내에 이러한 문제를 해결할 수 있으며, 이는 사실상 현재의 모든 표준 PKI를 무력화함을 의미한다[S3].

격자 기반 암호 (Lattice-based Cryptography)

격자 기반 암호는 고차원 공간 내에서 격자(Lattice)의 기저 벡터로부터 특정 지점을 찾는 문제(예: SVP, LWE)를 난제로 사용한다. 이 문제들은 최악의 경우(worst-case)에도 풀기 어렵다는 것이 증명되어 있으며, 평균적인 경우(average-case)에도 보안이 보장된다[S4].

포스트퀀텀 표준 (ML-KEM/ML-DSA)

• ML-KEM (Module-Lattice-based Key-Encapsulation Mechanism): 키 캡슐화 메커니즘으로, 효율적인 구현과 함께 격자 기반 난제를 사용하여 양자 내성을 제공한다.
• ML-DSA (Module-Lattice-based Digital Signature Algorithm): 전자 서명 표준으로, 격자 기반 수학 구조를 사용하여 강력한 서명 무결성을 보장한다. 격자 기반 시스템은 현재 표준화 과정에서 강력한 worst-case to average-case 환산성과 효율적인 성능을 입증하여 PQC 전환의 중심이 되고 있다[S4].