LWE, Lattice, Reduction 이해하기

📘 LWE, Lattice, Reduction 이해하기

1. LWE (Learning With Errors)

정의

• 문제: 비밀 벡터 s ∈Zqn를 찾는 문제.
• 주어진 식은 정확하지 않고 작은 오차(error) 가 포함된 선형방정식들.
  • (a, a⋅s+e) where a∈Zqn,  e∼χ
• 목표: 여러 샘플로부터 비밀 s를 추측.

왜 어려운가?

• 오차가 없다면 → 가우스 소거법으로 쉽게 풀림.
• 오차가 있으면 → 소거 과정에서 잡음이 증폭되어 비밀을 알아낼 수 없음.

활용

• 양자 이후(Post-Quantum) 암호의 핵심 기반:
  • 키 캡슐화 (KEM), 전자서명
  • 동형암호, 속성 기반 암호
  • 영지식증명

---

2. Lattice (격자)

정의

• 격자(Lattice): 선형독립 벡터 e1,…,em로 생성된 이산 집합.
• 벡터공간과 유사하지만 불연속적(discrete) 구조.

중요성

• 정수론적 성질을 고차원으로 확장 가능.
• 예: 정수환 Z를 1차원 격자로 보고, 이를 고차원 격자로 일반화.
• 대표 정리: 페르마 두 제곱 정리 (소수 p ≡ 1(mod 4)는 두 제곱수 합으로 표현 가능).

관련 문제

• SVP (Shortest Vector Problem): 가장 짧은 벡터 찾기 → NP-hard.
• SIVP (Shortest Independent Vector Problem): 가장 짧은 독립 벡터 집합 찾기 → 역시 어려움.
• 실제로는 근사 문제(Approximate SVP/SIVP)를 다룸.
• LLL 알고리즘 등으로 다차원 격자 근사 해법 존재.

격자의 기하학

• 벡터공간처럼 격자도 기저(basis)가 유일하지 않음.
• 비직교(non-orthogonal) 기저 → 격자의 기하학적 성질(예: 최단 벡터) 파악이 어려워짐.

Successive Minima (연속 최소치)

• 정의:
  • 원점 중심 반지름 r의 구를 생각했을 때,
  • i번째 최소치 λi(L): 구 안에 포함되는 i개의 선형독립 벡터가 존재하는 최소 반지름.
  • 격자의 구조를 측정하는 핵심 지표, 특히 λ1은 최단 벡터 길이.
• λ1(L): 격자의 가장 짧은 비영벡터 길이.
• 이는 격자 점들 사이의 최소 거리와 동일.특수한 경우:

---

3. Reduction (환원)

개념

• 문제 A → 문제 B 환원:
  문제 A를 문제 B로 변환해 풀 수 있으면, B를 풀면 A도 해결 가능.
• 중요성: 한 문제의 난이도를 다른 문제로 증명 가능.

예시

• 3SAT가 NP-hard임을 알면, 3SAT을 Independent Set 문제로 환원 → Independent Set도 어렵다고 결론.

---

4. LWE와 Lattice의 연결

• LWE의 난이도는 단순한 경험적 어려움이 아니라 격자 문제의 난이도와 연결됨.
• Regev의 결과:
  • LWE를 효율적으로 풀 수 있다면,
  • GapSVP, SIVP 같은 격자 문제를 양자 알고리즘으로 풀 수 있음.
• 즉, LWE의 안전성 = 격자 기반 난제의 안전성.
• 이것이 LWE가 양자 안전 암호(Post-Quantum Cryptography)핵심이 되는 이유.

---

✅ 정리

• LWE: 작은 오차가 있는 선형방정식 문제, Post-Quantum 암호의 핵심.
• 난이도: 단순 연산이 아닌 격자 문제 환원을 통해 정당화.
• Lattice: 이산적 벡터 공간 구조, 정수론과 깊게 연결.
• Successive Minima: 격자의 구조를 측정하는 핵심 지표, 특히 λ1은 최단 벡터 길이.