ML-KEM 및 ML-DSA 표준 이해

ML-KEM 및 ML-DSA 표준 이해

1. 격자 기반 암호의 부상

현재 실무적 표준화를 주도하는 것은 격자 기반(Lattice-based) 시스템이다. 이는 최악의 사례(worst-case)에서 평균적인 사례(average-case)로의 강력한 수학적 환산(reductions)이 존재하며, 효율적인 구현이 가능하기 때문이다 [S4]. 반면, 코드 기반(Code-based)이나 해시 기반(Hash-based) 방식은 보수적인 닻(conservative anchors) 역할을 수행하며, 더 긴 보안 이력이나 최소한의 가정만을 요구하는 특성을 갖는다 [S4].

2. ML-KEM (Module-Lattice Key Encapsulation Mechanism)

ML-KEM은 이전에 Kyber로 알려졌던 알고리즘에 기반한다. 모듈 격자 문제(Module Learning With Errors, MLWE)를 기반으로 하며, 다음과 같은 흐름을 가진다.

• KeyGen: 모듈 격자 내에서 공개키와 비밀키를 생성.
• Encapsulation: 공개키를 사용하여 공유 비밀값(Shared Secret)과 캡슐화된 키(Ciphertext)를 생성.
• Decapsulation: 비밀키를 사용하여 캡슐화된 키로부터 원래의 공유 비밀값을 복구.

3. ML-DSA (Module-Lattice Digital Signature Algorithm)

ML-DSA는 Dilithium에 기반하며, ‘Fiat-Shamir with Aborts’ 기법을 사용한다. 격자 문제의 어려움을 통해 위조 저항성을 제공하며, 서명 크기와 공개키 크기 사이의 균형을 맞춘 실용적인 표준이다.

4. 보안 가정

격자 기반 시스템의 안전성은 가장 짧은 벡터를 찾는 문제(Shortest Vector Problem, SVP)와 밀접하게 연관되어 있다. 양자 컴퓨터의 ‘쇼어 알고리즘(Shor’s Algorithm)’이 기존 RSA나 ECC를 효율적으로 깨는 것과 달리, 격자 문제는 양자 알고리즘으로도 다항 시간 내에 풀리지 않는다고 가정한다.