노트북 15 — Shor vs. 격자

노트북 15 — Shor vs. 격자#

마무리 장: 방금 구현한 알고리즘이 왜 ML-KEM은 깨지 못하는가.

Shor의 비밀: order finding으로의 환원#

정수 인수분해와 이산 로그 모두 어떤 군 원소의 곱셈에 대한 order를 찾는 문제로 환원됩니다. 양자 속도 향상은 한 가지 특수한 trick에서 나옵니다: \(\mathbb{Z}_N\) 위의 QFT는 어떠한 고전 Fourier 변환보다도 지수적으로 빠르게 주기성을 포착합니다. 이 trick은 기저 문제에 QFT가 붙잡을 수 있는 주기적(또는 더 일반적으로 군론적) 구조가 있을 때에만 성립합니다.

Hidden Subgroup Problem (HSP)#

인수분해와 이산 로그는 모두 Abelian Hidden Subgroup Problem의 특수한 경우입니다: 군 \(G\)의 부분군 \(H\)의 coset 위에서 상수인 함수 \(f: G \to S\)가 주어졌을 때, \(H\)를 찾는 문제입니다. \(G\)가 abelian일 때 — \((\mathbb{Z}_N, +)\), \((\mathbb{Z}_N^*, \times)\) — QFT가 군 대수(group algebra)를 대각화하며, 알고리즘이 효율적으로 돌아갑니다. RSA, Diffie-Hellman, ECDH가 모두 Shor에 무너지는 이유도 여기에 있습니다: 이들은 모두 Abelian HSP의 변장된 모습입니다.

LWE는 HSP 문제가 아닙니다#

Learning With Errors 문제는 다음을 묻습니다: 작은 오차 \(e_i\)를 갖는 많은 샘플 \((\mathbf{a}_i, \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \bmod q)\)가 주어졌을 때 \(\mathbf{s}\)를 복원하라. 여기에는 숨겨진 부분군이 없습니다 — 샘플과 비밀 사이의 관계는 주기적이 아니라 선형 + 가법적 노이즈입니다. 그 어떤 자연스러운 군 위의 QFT도 \(\mathbf{s}\)를 드러내지 못합니다. Shor가 활용하는 환원 자체가 적용되지 않습니다.

격자에 대해 알려진 양자 알고리즘#

그렇다면 무엇을 알고 있을까요? LWE와 관련된 격자 문제에 대한 가장 알려진 양자 알고리즘은 세 가지 갈래로 나뉩니다:

  • (a) Sieving에 양자 속도 향상을 더한 BKZ — 가장 안쪽 루프에 Grover 스타일의 제곱근 개선을 적용합니다. 전체적으로는 여전히 지수적입니다.

  • (b) Dihedral Hidden Subgroup Problem — LWE는 (non-abelian) dihedral HSP로 환원됩니다. 알려진 최고의 dihedral HSP 알고리즘은 sub-exponential이지만(Kuperberg), 다항 시간 양자 알고리즘은 없습니다.

  • (c) 양자 sieve 변형들 — Laarhoven 등은 적당한 속도 향상을 동반한 양자 격자 sieving을 제안했습니다. 그 어느 것도 지수 벽을 허물지는 못합니다.

ML-KEM의 파라미터는 이 모든 것을 염두에 두고 선택되었습니다.

이 사실이 당신에게 중요한 이유#

만약 내일 누군가가 LWE에 대한 효율적인 양자 알고리즘을 발견한다면, ML-KEM은 무너집니다. 이것은 추측된 난이도이지 증명된 난이도가 아닙니다. 그래서 우리는 하이브리드(X25519 + ML-KEM)로 배포합니다 — 둘 중 하나만 살아남아도 안전합니다. 같은 이유로 NIST는 SLH-DSA(해시 기반 서명)도 병행해 표준화했습니다 — 해시 기반 암호는 오직 충돌 저항성에만 의지하며, Shor나 그 후손이 공격할 만한 대수적 구조가 전혀 없습니다.

닫히는 서사#

  • 00a가 경고했습니다: Shor가 RSA와 ECC를 깬다.

  • 노트북 01–09가 만들었습니다: ML-KEM, 양자 안전으로 추측되는 방식.

  • 노트북 12–14가 보여 주었습니다: Shor는 실제로 RSA를 깬다 — 여기 돌아가는 코드가 있다.

  • 이번 장이 설명합니다: 그리고 같은 trick이 왜 ML-KEM은 깨지 못하는지.

암호학 세계는 격자 문제가 양자 공격자에 대해서도 계속 어려울 것이라는 데 판돈을 걸고 있습니다. 이 내기는 근거가 있지만 증명된 것은 아닙니다. 그래서 헤지로 하이브리드 배포가 있고, 백업으로 해시 기반 서명이 있으며, 장기전으로 지속적인 연구가 있습니다.

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

더 읽을거리#

  • Peter Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (1994).

  • Oded Regev. On Lattices, Learning With Errors, Random Linear Codes, and Cryptography (2005) — 그리고 The Learning with Errors Problem survey.

  • Greg Kuperberg. A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem (2005).

  • Chris Peikert. A Decade of Lattice Cryptography (2016).

  • NIST FIPS 203, 204, 205 (2024).