노트북 19 — ML-KEM 파라미터와 estimator

내용

노트북 19 — ML-KEM 파라미터와 estimator#

마무리 장입니다. \(n \le 15\)에서는 우리 primal 공격이 수 초 안에 성공하는 모습을 보았습니다. ML-KEM-512의 유효 격자 차원은 약 \(800\)입니다. 이번 노트북은 커뮤니티 표준 도구인 lattice estimator를 이용해 그 간극이 어떻게 완벽한 안전으로 이어지는지 설명합니다.

ML-KEM의 수치는 어디서 왔는가#

ML-KEM-512 파라미터 (FIPS 203):

\(n = 256\) (다항식 환 차원)
\(k = 2\) (module rank)
\(q = 3329\)
\(\eta_1 = 3, \eta_2 = 2\) (CBD 노이즈 파라미터)

Primal 공격 격자의 차원은 대략 \(n \cdot k + m = 256 \cdot 2 + 256 = 768\) 정도입니다. 이 위에서 \(\beta\)를 충분히 크게 하여 충분히 짧은 벡터를 보는 BKZ를 돌리는 것이 위협 모델입니다.

Lattice estimator#

Albrecht, Player, Scott(2015, 2024년까지 확장)는 Python 도구 — lattice-estimator — 를 만들었습니다. 주어진 LWE/MLWE instance에 대해 알려진 모든 공격(primal, dual, hybrid, BKW 및 변형)의 예상 비용을 계산합니다. NIST는 이 도구를 사용해 ML-KEM의 파라미터를 확정했습니다.

프로젝트에서 공개한 수치로부터 가져온 ML-KEM-512 예시 출력:

공격	\(\beta\)	Log cost
primal	400	143
dual	388	143
hybrid	411	141

Log cost 143은 대략 \(2^{143}\) 연산을 의미합니다 — AES-143을 무차별 대입으로 깨는 것에 해당합니다. ML-KEM-1024의 수치는 약 \(2^{272}\)입니다.

우리 장난감 수치 vs 현실#

Instance	격자 차원	사용한 \(\beta\)	Python 시간	Log cost (estimator)
우리의 장난감 LWE, \(n = 10\)	31	4	약 3 s	(임계값 이하)
우리의 장난감 LWE, \(n = 15\)	46	4	약 10 s	약 30
우리의 장난감 LWE, \(n = 25\)	76	약 10 (순수 Python으로는 비현실적)	—	약 55
ML-KEM-512	약 768	400	—	143
ML-KEM-768	약 1152	623	—	207
ML-KEM-1024	약 1536	832	—	272

“수 초면 가능”에서 “우주의 열사망 시점에도 불가능”으로의 도약은 \(\beta\)를 따라 매끄럽게 일어나지만, 체감상으로는 하나의 벽입니다. 이는 Part 4의 Shor 분석이 넘지 못한 그 벽과 같은 벽입니다 — 고전이든 양자든, 오늘날 두 경우 모두 ML-KEM 파라미터는 안전합니다.

이 수치를 믿는 이유#

Estimator는 2024년 기준 공개적으로 알려진 모든 공격을 반영합니다. 최근의 양자 sieve 속도 개선 포함.
NIST 표준화 과정은 외부 암호해독을 초청했습니다. 후보 축소가 두 라운드 진행되었고(Rainbow, SIKE 해독 포함), 이 과정에서 “안전”이 무엇인지에 대한 기준이 자리 잡았습니다.
143-bit의 안전 여유는 NIST의 “category 1” 임계값(대체로 AES-128 보안에 해당) 이상입니다.
헤징: 그럼에도 우리는 ML-KEM을 X25519와의 하이브리드로 사용합니다. 내일 누군가 더 나은 격자 공격을 발견해도, Shor가 도착할 때까지 고전 쪽 절반이 공유 비밀을 계속 보호합니다.

이것이 어떻게 연결되는가#

Part 1–4는 scheme을 만들고 긍정 사례를 따라갔습니다: ML-KEM은 이렇게 동작합니다.

Part 5는 공격자의 관점을 따라갔습니다: 우리라면 이렇게 공격할 것이고, 작은 파라미터에서는 여기까지 갑니다.

이 둘의 결합 — “우리는 만들었고, 우리는 공격했고, 우리는 벽이 어디 있는지 안다” — 이 바로 어떤 암호 시스템에 대한 운영상의 신뢰가 어떤 모습인지 보여줍니다. 몇 년 뒤면 모든 TLS handshake가 이 수학을 수행하게 됩니다. 이제 당신은 그 내부에서 무슨 일이 벌어지는지 압니다.

더 읽을거리#

lattice-estimator (Albrecht et al.): malb/lattice-estimator — 임의의 LWE/MLWE instance에 대한 비용 계산 도구.
NIST IR 8413 — ML-KEM 표준화 보고서, 부록 A가 파라미터 선택을 다룹니다.
Albrecht, Player, Scott. On the Concrete Hardness of Learning with Errors, JoMC 2015.
Chen & Nguyen. BKZ 2.0: Better Lattice Security Estimates, ASIACRYPT 2011.
Peikert. A Decade of Lattice Cryptography (2016) — survey.
Kannan. Improved Algorithms for Integer Programming and Related Lattice Problems, STOC 1983 — 원래의 embedding 논문.

19개의 노트북을 끝까지 읽어 주셔서 감사합니다.