노트북 11 — 배포, FAQ, 용어집

노트북 11 — 배포, FAQ, 용어집#

2026년 현재 PQC가 실제로 어디에서 돌아가고 있는지, 흔한 오해, 그리고 용어 참조입니다.

Part A — 실제 배포 현황 (2026)#

웹 / TLS#

  • Chrome, Edge: hybrid X25519Kyber768 (draft-tls-westerbaan) 가 Chrome 124 (2024년 4월) 이후 기본 활성화되어 있습니다. 2025년부터는 X25519MLKEM768 (FIPS 203 버전) 으로도 확산되고 있습니다.

  • Cloudflare: 2024년 말부터 edge TLS 1.3에서 X25519MLKEM768 이 사용 가능합니다. 오늘날 전체 연결의 약 15% 정도가 PQ hybrid를 사용합니다.

  • AWS KMS, Amazon s2n-tls, Google ALTS: 모두 hybrid 배포를 하고 있으며, Google 내부 트래픽은 수 년째 PQ-hybrid 로 운영되고 있습니다.

메시징#

  • Apple iMessage PQ3 (2024년 2월): 소비자 제품에서 최초로 폭넓게 배포된 PQ key agreement 입니다. KEM을 사용합니다 (자체 구성, ML-KEM으로 진화 중).

  • Signal PQXDH (2023년 9월): post-quantum extended triple Diffie-Hellman, hybrid CRYSTALS-Kyber를 사용합니다.

  • WhatsApp, Telegram: 마이그레이션 계획을 발표했으며, 상태는 다양합니다.

펌웨어 / 코드 서명#

  • Microsoft, Google Android: 인증 기관과 펌웨어 서명에 ML-DSA를 적용하고 있습니다.

  • FIDO2 / WebAuthn: PQ 확장을 표준화 중입니다 (2025).

Part B — 마이그레이션 전략#

Hybrid 먼저, PQ-only는 나중에. 2024–2026년의 모든 프로덕션 배포는 hybrid입니다: 고전 (X25519 또는 ECDSA) 과 post-quantum (ML-KEM 또는 ML-DSA) 을 병렬로. 공유 비밀이나 signature는 양쪽 모두가 유효할 때만 유효합니다. 이를 통해 얻는 것:

  • 새 PQ 방식에 대한 예상치 못한 암호분석으로부터의 안전성.

  • 하위 호환성 — 상대가 PQ를 이해하지 못하면 고전으로 협상 다운그레이드.

Crypto agility. RSA/ECDSA를 하드코딩한 애플리케이션은 마이그레이션이 고통스럽습니다. 교훈: 키/signature 타입을 알고리즘 식별자 뒤에 감싸서 교체가 코드 재작성이 아닌 설정 변경이 되도록 하세요.

Harvest-now-decrypt-later (HNDL) 우선순위:

  1. 수명이 긴 기밀 데이터 (의료 기록, 법률 문서, 정부). 지금 마이그레이션.

  2. 수명이 짧은 임시 트래픽용 세션 키 (웹 브라우징). 덜 시급함.

  3. 신원 및 서명 키 (인증서): 5–10년의 전환 계획.

Part C — FAQ와 흔한 오해#

Q: “Grover 알고리즘이 AES를 깬다.” A: 아닙니다. Grover는 quadratic speedup을 제공합니다. AES-128은 128비트 안전성에서 대략 64비트 양자 안전성으로 떨어집니다; AES-256은 약 128비트 양자 안전성을 유지합니다. 키 크기를 두 배로 하고 넘어가면 됩니다. 대칭 암호는 괜찮습니다.

Q: “PQC는 느리고 거대하다.” A: 반반입니다. 최적화된 C에서 ML-KEM-768은 약 50 μs에 encapsulation을 수행합니다 — RSA-2048보다 빠릅니다. 암호문은 1088바이트입니다 (X25519의 32바이트 대비) — 눈에 띄게 크지만 고통스러울 정도는 아닙니다. ML-DSA signature는 ECDSA 의 64 B 대비 약 3 KB 입니다 — 이것이 진짜 크기 비용입니다. SPHINCS+ signature는 40 KB 에 이를 수 있습니다 — 비싸고, 그래서 가능한 경우 ML-DSA를 선호합니다.

Q: “양자 컴퓨터는 30년 뒤의 일인데, 왜 서두르나?” A: 세 가지 이유: (1) 아무도 모릅니다 — 타임라인은 추측입니다. (2) Harvest-now-decrypt-later 는 오늘의 데이터에 대한 공격이 Q-Day에 일어날 수 있음을 의미합니다. (3) 인터넷 규모의 마이그레이션은 방법을 알고 있어도 5–10년이 걸립니다. 2024년에 시작해야 여유가 생깁니다.

Q: “양자가 RSA를 깬다면, 결국 ML-KEM도 깨지 않을까?” A: 가능성은 있습니다. Lattice 기반 암호는 약 30년의 연구를 거쳤습니다; 다항 시간의 양자 또는 고전 공격은 발견되지 않았고, worst-case-to-average-case reduction 이 있습니다 (LWE를 평균적으로 푸는 것은 최악의 경우 lattice 문제를 푸는 것만큼 어렵다 — 이례적으로 강한 보장). 그렇다 해도 “아직 공격이 없다”가 “영원히 공격이 없다”는 아닙니다. 그래서 hybrid 배포를 사용하며, 오직 hash function 안전성에만 기반한 백업으로 SLH-DSA도 함께 표준화합니다.

Q: “대칭 암호도 교체해야 하나?” A: 아닙니다. AES-GCM / ChaCha20-Poly1305 를 유지하세요. 비대칭 키 합의만 post-quantum으로 바꾸면 됩니다.

Q: “왜 ML-KEM의 공개키는 800바이트인데 ECDH는 32바이트인가?” A: Lattice KEM은 Z_q에서 k×n 계수 벡터를 인코딩합니다. ML-KEM-512의 경우: k=2, n=256, 각 계수 12비트 → 2·256·12/8 = 768 바이트, 여기에 32바이트 seed. ECDH는 하나의 curve point (32바이트) 만 보냅니다. 이것은 lattice 방식의 구조적 비용입니다 — 극적으로 줄일 수 있는 알려진 방법은 없습니다.

Part D — 용어집 (빠른 참조)#

용어

의미

BDD

Bounded Distance Decoding. 목표점이 lattice에 가깝다고 보장된 CVP. LWE는 BDD로 환원됩니다.

CBD

Centered Binomial Distribution. ML-KEM이 작은 잡음을 샘플링하는 방식.

CVP

Closest Vector Problem. 주어진 목표점에 가장 가까운 lattice 점을 찾는 문제.

Encapsulation / Decapsulation

KEM 연산. Encaps는 (K, ct) 를 생성; Decaps는 ct 와 개인키로부터 K 를 복구.

FIPS 203 / 204 / 205

ML-KEM, ML-DSA, SLH-DSA에 대한 NIST 표준.

FO transform

Fujisaki-Okamoto. IND-CPA PKE를 IND-CCA2 KEM으로 변환.

Grover’s algorithm

양자 검색. Quadratic speedup — 대칭 실효 안전성을 절반으로 만듭니다.

Hybrid

두 개의 KEM (또는 signature) 을 병렬로 실행 — 예: X25519 + ML-KEM.

IND-CCA2

Indistinguishability under adaptive chosen-ciphertext attack. KEM의 목표.

IND-CPA

Indistinguishability under chosen-plaintext attack. ML-KEM 내부의 K-PKE가 단독으로 달성하는 수준.

KAT

Known Answer Test. 바이트 단위 준수 검증을 위해 NIST가 공표하는 test vector.

KEM

Key Encapsulation Mechanism. 공유 비밀을 만드는 공개키 프로토콜.

K-PKE

ML-KEM 내부 에 있는 IND-CPA 공개키 암호화 방식.

Lattice

{B·z : z in Z^d} — 공간 상의 이산적이고 규칙적인 점 격자.

LWE

Learning With Errors. 잡음이 있는 선형 샘플 (a, <a,s> + e) 로부터 s를 찾는 문제.

ML-DSA

Module-Lattice Digital Signature Algorithm. FIPS 204. Dilithium 의 새 이름.

ML-KEM

Module-Lattice KEM. FIPS 203. Kyber 의 새 이름.

Module-LWE (MLWE)

Polynomial 벡터 상의 LWE. ML-KEM의 난해성 가정.

NTT

Number-Theoretic Transform. Z_q 상의 FFT; polynomial 곱셈을 O(n log n) 으로 만듭니다.

PKE

Public-Key Encryption. 공개키로 암호화, 개인키로 복호화.

PRF

Pseudo-Random Function. 키가 있고, 출력이 랜덤과 구별 불가능.

PRNG

Pseudo-Random Number Generator.

PQC

Post-Quantum Cryptography. 양자 컴퓨터에 대해 안전하리라 여겨지는 방식들.

Q-Day

암호학적으로 의미 있는 양자 컴퓨터가 존재하는 날. 날짜 미상.

Ring-LWE (RLWE)

단일 polynomial ring 상의 LWE. MLWE의 전신.

R_q

Z_q[x] / (x^n + 1). ML-KEM이 사용하는 polynomial ring (q=3329, n=256).

Shor’s algorithm

인수분해와 discrete log에 대한 양자 다항 시간 해법. RSA/ECC를 깨뜨립니다.

SIS

Short Integer Solution. LWE의 형제 격 난해성 가정 — ML-DSA가 사용.

SLH-DSA

Stateless Hash-Based DSA. FIPS 205. SPHINCS+ 의 새 이름.

SVP

Shortest Vector Problem. lattice에서 가장 짧은 0이 아닌 벡터를 찾는 문제.

XOF

Extendable-Output Function. 가변 길이 출력을 내는 hash. SHAKE-128/256.

더 읽을거리#

  • FIPS 203 — ML-KEM 표준 (NIST 2024). 권위 있는 원문.

  • Peikert, A Decade of Lattice Cryptography (2016) — 조사 수준.

  • Albrecht, Player, Scott, On the concrete hardness of Learning With Errors — LWE estimator.

  • Bernstein & Lange, Post-quantum cryptography (Nature Reviews, 2017) — 친절한 개괄.

  • PQCrypto conference — 연례 학술 행사.

  • pq-crystals.org — Kyber/Dilithium 팀의 사이트. 레퍼런스 코드 포함.

  • NIST PQC project page — 모든 후보, 공격, 코멘트의 아카이브.

읽어 주셔서 감사합니다#

여러분은 “lattice가 무엇인가?” 에서 시작해 테스트, 벤치마크, hybrid key exchange까지 갖춘 동작하는 ML-KEM 구현에 도달했습니다. 이제 향후 몇 년 내에 인터넷에서 Diffie-Hellman을 대체하게 될 암호에 대해 운용 수준의 이해를 갖추게 되었습니다.

버그, 오타, 불분명한 설명을 발견하셨다면 github.com/hulryung/ml-kem-notebooks 에 이슈를 열어주세요.