노트북 02 — LWE 문제

내용

노트북 02 — LWE 문제#

목표: 작은 예제를 통해 Learning With Errors (LWE) 를 실제로 다루어 봅니다. 손으로 샘플을 만들어 보고, Regev의 단일 비트 공개키 암호화를 처음부터 끝까지 실행해 봅니다.

한 단락으로 정리한 LWE#

Learning With Errors (LWE): 다음과 같은 많은 샘플

\[ (a_i, b_i = \langle a_i, s \rangle + e_i \bmod q) \]

이 주어졌을 때 — 여기서 \(s \in \mathbb{Z}_q^n\) 은 고정된 비밀값, 각 \(a_i \in \mathbb{Z}_q^n\) 은 균등 난수, 각 \(e_i\)는 작은 가우시안 노이즈입니다 — \(s\)를 복원하는 문제입니다.

결정(decision) 버전: 실제 LWE 샘플을 균등하게 임의적인 \((a, b)\)와 구별하는 문제입니다. search-LWE와 decision-LWE 둘 다 어렵다고 추측되며, 최악의 경우의 격자 문제로 증명 가능하게 환원됩니다.

import numpy as np
rng = np.random.default_rng(1)
n, q, sigma = 4, 17, 1.0
s = rng.integers(0, q, n)
a = rng.integers(0, q, n)
e = int(np.round(rng.normal(0, sigma)))
b = (int(a @ s) + e) % q
print('s =', s)
print('a =', a)
print('<a,s> =', int(a @ s), 'mod', q, '=', int(a @ s) % q)
print('e =', e)
print('b =', b)

s = [ 8  8 12 16]
a = [ 0  2 13 16]
<a,s> = 428 mod 17 = 3
e = 1
b = 4

Regev의 단일 비트 공개키 암호화#

키 생성(Key generation). 비밀값 \(s \in \mathbb{Z}_q^n\) 과 \(m\)개의 LWE 샘플을 생성합니다. 공개키는 \((a_i, b_i)\) 쌍들의 목록입니다.

암호화(Encrypt), 비트 \(\mu \in \{0, 1\}\)에 대해: 샘플들의 부분집합 \(S\)를 임의로 골라 다음을 출력합니다.

\[ (a^*, b^*) = \Big( \sum_{i \in S} a_i \bmod q,\ \sum_{i \in S} b_i + \mu \cdot \lfloor q/2 \rfloor \bmod q \Big). \]

복호화(Decrypt), \(s\)를 사용해: \(v = b^* - \langle a^*, s \rangle \bmod q\) 를 계산합니다. \(v\)가 \(0\)에 가까우면 \(0\)을 출력하고, \(q/2\)에 가까우면 \(1\)을 출력합니다.

정확성: \(v = \sum_{i \in S} e_i + \mu \lfloor q/2 \rfloor\) 이며, 이는 작은 노이즈 항에 \(0\) 또는 \(q/2\)가 더해진 값입니다. 누적된 노이즈의 크기가 \(q/4\) 미만으로 유지되면 복호화는 명확하게 이루어집니다.

from pqc_edu.lwe import toy_keygen, toy_encrypt, toy_decrypt
rng = np.random.default_rng(0)
pk, sk = toy_keygen(n=16, q=257, sigma=1.0, rng=rng)
print('secret key s:', sk.s)
print('public key has', pk.samples.shape[0], 'samples, each',
      pk.samples.shape[1] - 1, 'coefficients + b')

secret key s: [218 163 131  69  79  10  19   4  45 209 166 234 129 155 249 187]
public key has 42 samples, each 16 coefficients + b

results = []
for _ in range(20):
    bit = int(rng.integers(0, 2))
    ct = toy_encrypt(pk, bit, rng)
    recovered = toy_decrypt(sk, ct)
    results.append((bit, recovered, bit == recovered))
print(f"{'bit':>5} {'decrypted':>10} {'ok':>5}")
for b, r, ok in results:
    print(f"{b:>5} {r:>10} {str(ok):>5}")
print('all correct?', all(ok for _, _, ok in results))

  bit  decrypted    ok
        0  True
        0  True
        0  True
        1  True
        0  True
        1  True
        1  True
        1  True
        1  True
        1  True
        1  True
        1  True
        1  True
        0  True
        1  True
        1  True
        0  True
        1  True
        0  True
        0  True
all correct? True

노이즈 예산 시연#

\(\sigma\)가 너무 크면 복호화에 실패할 수 있습니다. 무작위로 고른 샘플의 부분합에서 누적된 오차가 \(b^*\)를 \(0\)이나 \(\lfloor q/2 \rfloor\) 주변의 명확한 영역 바깥으로 밀어낼 수 있습니다. 실제 방식들은 실패 확률이 무시할 정도로 작게(일반적으로 \(2^{-100}\) 훨씬 아래) 파라미터를 신중하게 고릅니다.

rng = np.random.default_rng(0)
pk, sk = toy_keygen(n=16, q=257, sigma=8.0, rng=rng)
fails = 0
for _ in range(200):
    bit = int(rng.integers(0, 2))
    ct = toy_encrypt(pk, bit, rng)
    if toy_decrypt(sk, ct) != bit:
        fails += 1
print(f'failures: {fails}/200 with sigma=8.0')

failures: 3/200 with sigma=8.0

이 토이 방식의 문제점#

이 구성은 정확하지만 실용적이지는 않습니다.

암호문당 1비트는 낭비입니다(평문 1비트에 대해 암호문이 약 \(n \log q\) 비트).
공개키 행렬이 너무 큽니다 — \(\mathbb{Z}_q\)의 원소로 된 \(m \times n\)개의 항목.
능동적 공격자에 대한 보호가 없습니다 — 악의적인 암호문이 \(s\)를 드러낼 수 있습니다.

ML-KEM (노트북 06)은 세 가지 모두를 해결합니다: 컴팩트한 키를 위한 module lattice, 빠른 다항식 곱셈을 위한 NTT, 그리고 CCA 보안을 위한 Fujisaki-Okamoto 변환입니다.

그 전에 먼저 질문: 실제로 토이 LWE를 깰 수 있을까요? → 03_attacking_toy_lwe.ipynb.