LWE (Learning With Errors)

📌 LWE (Learning With Errors)

• 정의:
  비밀 벡터 s∈Zqn를 약간의 오차(Noise)가 포함된 선형 방정식 집합으로부터 복원하는 문제.
  샘플은 다음과 같은 형태:(a,b=⟨a,s⟩+e(modq))
  • 여기서 a는 균등 분포, e는 작은 오차(에러 분포 χ).
• 난이도
  
  • 오차가 없으면 가우스 소거로 쉽게 해결 가능.
  • 오차가 있으면 소거 과정에서 잡음이 증폭되어 비밀 벡터를 구하기 어려움

---

📌 격자 문제와의 연결

• 격자(Lattice): 선형 독립 벡터들의 정수 계수 조합으로 생성된 이산적 점 집합.
• 대표 문제들:
  • SVP (Shortest Vector Problem): 가장 짧은 벡터 찾기
  • SIVP (Shortest Independent Vectors Problem): 독립적인 짧은 벡터 집합 찾기
  • GapSVP: 근사 최단 벡터 판별 문제

•  

이 문제들은 NP-hard로 알려져 있고, 암호학적 안전성의 기반이 됨.

---

📌 Regev의 환원 (2005)

• 주요 결과
  
  • Regev은 최악-경우 격자 문제(GapSVP, SIVP)를 평균-경우 LWE 문제로 환원함.
  • 즉, LWE를 효율적으로 풀 수 있으면 격자 문제도 (양자 알고리즘으로) 풀 수 있음

• 의미
  
  • LWE는 최악-경우 격자 문제 난이도에 기반한 안전성을 가진다.
  • 따라서 LWE 기반 암호는 양자 컴퓨터에도 안전한 후양자 암호(Post-Quantum Cryptography)의 강력한 후보임.

---

📌 활용

• LWE는 다양한 암호 시스템의 기반
  • 키 캡슐화 (KEM)
  • 디지털 서명
  • 완전 동형암호 (FHE)
  • 속성 기반 암호 (ABE)
  • 영지식 증명 (ZKP)

•  

---

✅ 요약 정리:

• LWE는 "오차가 있는 선형 방정식으로부터 비밀 벡터를 찾는 문제"
• 오차 때문에 계산이 어려워지고, 이는 격자 문제 난이도와 연결됨
• Regev의 환원: LWE ≤ (양자) 격자 문제 → 안전성 보장
• 현재 후양자 암호학의 핵심 기반