노트북 01 — 격자(lattice)란 무엇인가?#
목표: 2차원 격자와 두 가지 핵심 난해 문제 — Shortest Vector Problem (SVP)과 Closest Vector Problem (CVP) — 에 대한 직관을 세웁니다.
격자 문제는 post-quantum cryptography (양자 내성 암호) 가 동작하는 이유입니다. 고차원에서는 알려진 어떤 다항 시간 양자 알고리즘으로도 풀리지 않기 때문입니다. 반면 Shor 알고리즘은 RSA와 타원곡선 암호를 단숨에 무너뜨립니다.
import numpy as np
import matplotlib.pyplot as plt
from pqc_edu.lattice import plot_lattice_2d, good_vs_bad_basis, lattice_points
형식적 정의#
선형 독립인 벡터들을 열로 가지는 기저 행렬 \(B \in \mathbb{R}^{d \times d}\)가 주어졌을 때, \(B\)가 생성하는 격자는 다음과 같습니다.
즉, 격자는 기저 벡터들의 모든 정수 조합의 집합입니다. 격자는 이산적이고, 무한하며, 규칙적으로 간격을 둔 점들의 격자망입니다.
plot_lattice_2d(np.eye(2), radius=4)
plt.title('Z^2: standard integer lattice')
plt.show()
좋은 기저 vs. 나쁜 기저#
같은 격자도 서로 다른 기저로 표현될 수 있습니다. 좋은(good) 기저는 짧고 거의 직교하는 벡터로 이루어져 있습니다. 나쁜(bad) 기저는 길고 비뚤어져서 거의 평행에 가까운 벡터들로 이루어져 있습니다. 두 기저는 정확히 같은 격자점 집합을 생성하지만, 알고리즘적으로 좋은 기저는 CVP를 쉽게 만들고 나쁜 기저는 어렵게 만듭니다. 격자 암호 해독의 상당 부분은 나쁜 기저를 좋은 기저로 바꾸는 작업(lattice reduction, 예: LLL과 BKZ)에 관한 것입니다.
good, bad = good_vs_bad_basis()
fig, axes = plt.subplots(1, 2, figsize=(10, 5))
plot_lattice_2d(good, 4, ax=axes[0])
axes[0].set_title('good basis')
plot_lattice_2d(bad, 4, ax=axes[1])
axes[1].set_title('bad basis')
plt.tight_layout()
plt.show()
두 가지 난해 문제#
Shortest Vector Problem (SVP): 격자 \(L\)의 기저가 주어졌을 때, 유클리드 길이가 최소인 0이 아닌 격자 벡터를 찾습니다.
Closest Vector Problem (CVP): 격자 \(L\)의 기저와 격자에 속하지 않는 목표 점 \(t \notin L\)이 주어졌을 때, \(t\)에 가장 가까운 격자 벡터를 찾습니다.
두 문제 모두 2차원에서는 쉽습니다(눈으로 찾을 수 있습니다). 그러나 고차원에서는 두 문제 모두 최악의 경우 NP-hard이며, 현재 알려진 최선의 알고리즘은 — 고전적이든 양자적이든 — 차원에 대해 지수 시간이 걸립니다.
target = np.array([2.3, 1.7])
plot_lattice_2d(good, 5, target=target)
plt.title('CVP: find closest lattice point')
plt.show()
왜 양자 컴퓨터에도 어려운가?#
Shor 알고리즘은 양자 컴퓨터에서 정수 소인수분해와 이산 로그 문제를 다항 시간에 풉니다 — 이것이 RSA, DH, ECC를 무너뜨립니다.
그러나 고차원에서 근사 SVP 또는 CVP를 다항 시간에 푸는 양자 알고리즘은 알려진 바 없습니다. 알려진 최선의 양자 가속은 고전적 지수 시간 알고리즘에 대해 다항식 수준의 개선에 불과합니다(예: Grover 방식).
다음 노트북에서 다룰 LWE는 CVP와 유사한 문제로 환원(reduce) 됩니다. 따라서 LWE를 깨는 것은 어려운 격자 문제를 깨는 것과 같습니다. 이것이 현대 PQC (ML-KEM, ML-DSA)의 기반입니다.
→ 다음: 02_toy_lwe.ipynb.