1. KEM (Key Encapsulation Mechanism)이란?

KEM은 양자 내성 암호(Post-Quantum Cryptography, PQC) 분야에서 중요한 역할을 하는 핵심 메커니즘입니다.

1.1. 공개키 암호 체계 (PKE)와의 비교

전통적인 공개키 암호화(PKE, Public Key Encryption) 방식은 앨리스(Alice)가 밥(Bob)의 공개키(pk)를 이용해 메시지(m)를 암호화(Enc(pk, m)하고, 밥이 자신의 비밀키sk)로 복호화(Dec(sk,ct) = m)하여 기밀성을 보장하는 방식입니다.

반면, KEM(Key Encapsulation Mechanism)은 PKE를 이용해 통신 당사자들이 대칭키 암호를 사용하기 전에 공통의 대칭키(K)를 공유하는 메커니즘입니다.

1.2. KEM의 안전성 정의

KEM의 안전성은 PKE와 마찬가지로 IND-CPA (Indistinguishability under Chosen-Plaintext Attack) 및 더 강력한 IND-CCA2 (Indistinguishability under Chosen-Ciphertext Attack) 게임을 통해 정의됩니다. 공격자의 승리 확률이 2^{-128} 수준으로 낮아야 안전하다고 간주됩니다.

2. PKE를 KEM으로 변환하는 방법 (Fujisaki-Okamoto Transform)

일반적인 방법은 IND-CPA 안전성을 갖는 PKE를 IND-CCA2 안전성을 갖는 KEM으로 변환하는 것입니다. 이 변환에 가장 널리 사용되는 것이 Fujisaki-Okamoto Transform (FO)입니다.

• FO 변환의 특징: IND-CPA 안전한 PKE만으로도 충분히 안전한(IND-CCA2) KEM을 만들 수 있습니다.
• 원리: 복호화(Decap) 과정에서 정상적으로 만들어진 암호문만 복호화하고, 그렇지 않은 경우 거부키(implicit rejection key)를 출력하여 비밀 정보 유출을 방지합니다.

3. 격자 기반 KEM의 발전 역사

격자 기반 암호는 LWE (Learning With Errors)와 LWR (Learning With Rounding) 문제에 기반하며, 이들의 Ring/Module 변형이 효율성을 높이는 데 사용됩니다.

• LWE (Learning With Errors): 가우시안 노이즈(Gaussian noise)를 추가하여 정의됩니다.
  • pk: (A, b = A dot s + e) 
• LWR (Learning With Rounding): 노이즈가 반올림(rounding) 과정에서 발생합니다.

격자 기반 KEM의 발전은 LWE/LWR의 다양한 변형을 통해 이루어졌습니다23.

4. 주요 격자 기반 KEM 상세 분석

4.1. ML-KEM (Kyber)

ML-KEM은 NIST 표준 버전 알고리즘으로 채택된 Crystals-Kyber의 이름입니다.

• 기반 난제: MLWE (Module LWE) 기반의 IND-CCA2 안전성.
• 구조: IND-CPA 안전한 ML-KEM.PKE에 FO Transform을 적용하여 IND-CCA2 안전한 ML-KEM.KEM을 구성합니다.
• 랜덤 요소: 비밀키(s), 랜덤니스(r), 노이즈(e) 모두 Centered Binomial Distribution (CBD)를 사용합니다.
• 복호화 실패 확률(DFP): Pr[Dec_sk (Enc(m)) != m]이 2^{-139} ~ 2^{-174} 수준으로 매우 낮습니다.

4.2. SMAUG-T

SMAUG-T는 (R)Lizard의 뒤를 잇는 모듈 격자 기반의 경량화된 알고리즘으로, 대한민국에서 개발에 참여하였습니다 (크립토랩, 서울대학교, 국군방첩사령부 등).

• 기반 난제: MLWE와 MLWR을 모두 기반으로 하는 IND-CCA2 안전성.
• 구조: MLWE 기반 공개키와 MLWR 기반 암호화를 조합한 SMAUG-T.PKE에 FO Transform을 적용합니다.
  • 이를 통해 LWE와 LWR 양쪽의 이점(높은 효율성)을 활용합니다.
• 랜덤 요소:
  • 비밀키(s): Fixed-weight sparse ternary (HWT).
  • 노이즈(e): Discrete Gaussian (dGaussian).
  • 랜덤니스(r): Sparse CBD (spCBD).
  • CBD를 대체하는 이 고효율 샘플러들(HWT, dGaussian, spCBD)을 통해 더 작은 사이즈와 복호화 실패 확률 감소를 달성했습니다.
• 복호화 실패 확률(DFP): Pr[Dec_sk (Enc(m)) != m]이 2^{-118} ~ 2^{-194} 수준입니다.
• 효율성: 128-bit 보안 파라미터 기준으로, SMAUG-T는 NIST Kyber 대비 암호문(CT)과 공개키(PK) 크기(bytes)를 합친 총 사이즈에서 더 효율적입니다 (SMAUG-T를 100%로 보았을 때 Kyber는 117% 수준).