노트북 05 — Ring-LWE와 Module-LWE

목표: LWE를 스칼라에서 다항식으로, 그리고 다시 다항식 벡터로 끌어올립니다.

Ring-LWE (RLWE) 는 LWE를 환 R_q = Z_q[x]/(x^n + 1) 안에서 다시 기술합니다. 비밀 s, 오차 e, 공개 계수 a가 모두 다항식입니다. 샘플은 (a, b = a.s + e) in R_q x R_q 입니다. 다항식 하나가 n개의 값을 담기 때문에, 하나의 RLWE 샘플이 기존 LWE 샘플 n개를 대체합니다.

import numpy as np
from pqc_edu.polyring import Poly
from pqc_edu.ntt import ntt, intt, pointwise_mul, poly_mul_ntt, Q, N
from pqc_edu.sampling import prf, cbd, sample_uniform

rho = b'\x01' * 32
sigma = b'\x02' * 32
a = sample_uniform(rho, 0, 0)          # uniform a in R_q (NTT domain)
s = cbd(prf(sigma, 0, N * 3 // 4), eta=3)  # small secret (time domain)
e = cbd(prf(sigma, 1, N * 3 // 4), eta=3)  # small error  (time domain)
s_hat = ntt(s)
# b_hat = a * s_hat + ntt(e), but since a is already in NTT domain:
b_hat = pointwise_mul(a, s_hat) + ntt(e)
print('a (first 5 coeffs, NTT dom):', a.coeffs[:5].tolist())
print('s (first 5 coeffs, time) :', s.coeffs[:5].tolist())
print('e (first 5 coeffs, time) :', e.coeffs[:5].tolist())
print('b (first 5 coeffs, NTT dom):', b_hat.coeffs[:5].tolist())

a (first 5 coeffs, NTT dom): [1590, 2952, 2536, 830, 2397]
s (first 5 coeffs, time) : [3328, 3328, 1, 3328, 3328]
e (first 5 coeffs, time) : [1, 2, 3327, 3327, 3327]
b (first 5 coeffs, NTT dom): [92, 925, 2929, 2360, 90]

왜 Module-LWE (MLWE) 인가? Ring-LWE의 강한 대수적 구조(단일 prime-power cyclotomic ring)는 일부 암호학자들을 불안하게 했습니다 — 자유도가 적다는 것은 보안 분석의 손잡이가 적다는 뜻이기 때문입니다. Module-LWE는 R_q^k에서 동작합니다: s와 e는 길이 k의 다항식 벡터이고, A는 k x k 다항식 행렬입니다. ML-KEM은 k가 {2, 3, 4} 중 하나를 사용합니다 — 일반 LWE의 일반성과 Ring-LWE의 효율성 사이의 절충입니다.

k = 2
rho = b'\x11' * 32
sigma = b'\x22' * 32
eta = 2

# Build k x k matrix A (in NTT domain)
A_hat = [[sample_uniform(rho, i, j) for j in range(k)] for i in range(k)]
# Secret s, error e: length-k vectors of small CBD polys
s = [cbd(prf(sigma, i, N*eta//4), eta) for i in range(k)]
e = [cbd(prf(sigma, k + i, N*eta//4), eta) for i in range(k)]
s_hat = [ntt(p) for p in s]
# t_hat = A_hat @ s_hat + ntt(e)
t_hat = []
for i in range(k):
    acc = Poly.zero(N, Q)
    for j in range(k):
        acc = acc + pointwise_mul(A_hat[i][j], s_hat[j])
    acc = acc + ntt(e[i])
    t_hat.append(acc)
print('Built MLWE public key t_hat with', k, 'polynomials, each of length', N)
print('first 5 coeffs of t_hat[0]:', t_hat[0].coeffs[:5].tolist())

Built MLWE public key t_hat with 2 polynomials, each of length 256
first 5 coeffs of t_hat[0]: [3111, 804, 3259, 1591, 989]

이것이 바로 ML-KEM이 사용하는 공개키 형태입니다: (A, t = A.s + e) 이고 s, e는 작은 값입니다. 다음 노트북에서는 이 위에 완전한 FIPS 203 K-PKE 암호화와 CCA 보안을 위한 Fujisaki-Okamoto 래퍼를 구현합니다. → 06_ml_kem_spec.ipynb.