노트북 09 — 우리가 만든 것

아홉 개의 노트북을 거치며 토이 LWE를 만들고, 작은 파라미터에서 그것을 깨뜨렸으며, 다항식 환 Z_q[x]/(x^n+1) 과 NTT가 왜 ML-KEM을 빠르게 만드는지 배웠고, FIPS 203 ML-KEM (512/768/1024)을 구현해 roundtrip과 크기 테스트를 통과시켰습니다.

한 단락 자가 점검

되돌아 보지 말고, 다음 내용을 담은 다섯 문장짜리 ML-KEM 설명을 적어 봅시다.

• 어떤 문제가 어려운가 (LWE / Module-LWE)

• 환(ring) 구조가 어떻게 도움이 되는가 (NTT, 컴팩트한 키)

• K-PKE가 무엇을 하는가 (공개키 (A, t = A s + e) 로 암호화)

• FO 변환이 왜 있는가 (CPA → CCA 보안으로 승격)

• shared secret이 무엇에서 유도되는가 (encapsulation된 메시지의 해시)

어느 하나라도 설명할 수 없다면, 그 항목의 노트북을 다시 읽어야 할 때입니다.

프로덕션 대비 부족한 점

• Constant-time 산술: 실제 구현은 비밀에 의존하는 분기나 메모리 접근을 피합니다. 우리 구현은 Python int와 numpy를 사용하는데, 이는 constant-time이 아닙니다.

• Side-channel 내성: cache timing, 전력, EM side channel에 대한 대응책. 본 자료의 범위를 벗어납니다.

• NIST Known-Answer Tests (KATs): FIPS 203 테스트 벡터와 bit-for-bit 동치성 검증은 하지 않았습니다(미묘한 byte-packing 차이로 wire-level 호환성이 깨질 수 있습니다). 우리 테스트는 self-consistency를 보여주는 것이지 interoperability를 보여주는 것은 아닙니다.

• 안전한 메모리 소거: Python에는 사용 후 메모리를 신뢰성 있게 0으로 만드는 이식 가능한 방법이 없습니다.

• 감사받은 의존성: 우리는 hashlib (문제 없음)과 numpy (속도 목적에 한함)에만 의존합니다.

더 읽을거리

• FIPS 203 — ML-KEM 표준 (NIST, 2024). 권위 있는 스펙.

• Regev 2005 — On Lattices, Learning With Errors, Random Linear Codes, and Cryptography (STOC’05). 최초의 LWE 논문.

• Peikert 2016 — A Decade of Lattice Cryptography. 포괄적 서베이.

• LWE Estimator (Albrecht, Player, Scott) — github.com/malb/lattice-estimator. 구체적 LWE 난이도를 평가하는 커뮤니티 표준 도구.

• kyber-py (Giacon) — 비교해 보고 싶다면 깔끔한 Kyber/ML-KEM 참조 Python 구현.

다음 단계

• ML-DSA (Dilithium, FIPS 204) — 같은 Module-LWE/SIS 기반의 격자 기반 서명.

• SLH-DSA (SPHINCS+, FIPS 205) — stateless 해시 기반 서명. 수학이 다릅니다: 해시 함수만 사용하며, 서명 크기는 훨씬 크지만 최소한의 가정만 필요합니다.

• BIKE / HQC / Classic McEliece — 코드 기반 KEM. NIST의 대체 트랙.

• 실전에서의 하이브리드 — draft-ietf-tls-hybrid-design을 읽고 다가오는 TLS 1.3 하이브리드 배포를 지켜보세요 (Chrome은 2023년부터 X25519+Kyber를 배포하고 있습니다).

실습 캡스톤: pq-messenger (한국어) — 방금 만든 pqc_edu ML-KEM을 사용해 X25519 + ML-KEM-768 하이브리드 X3DH 핸드셰이크와 완전한 Double Ratchet(대칭 체인 + DH 회전, v0.2부터)으로 동작하는 Signal 스타일의 종단 간 암호화 CLI입니다. 두 개의 실제 OS 프로세스, 공유 파일 큐, 그리고 모든 바이트가 보이는 구조.