📘 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로 생성된 이산 집합.벡터공간과 유사하지만 불연속적(discre..

1. 나눗셈 정리 (Division Theorem)정의임의의 정수 a, 양의 정수 n에 대해,유일한 정수 q,r이 존재하여 다음을 만족: a=nq+r, 0≤rq: 몫(quotient)r: 나머지(remainder)예시a=39,  n=7 ⇒ q=5,  r=4 a = 39, 39 = 7 × 5 + 4.2. 자연수의 최소원리 (Well-Ordering Principle)정의자연수 집합 N의 임의의 공집합이 아닌 부분집합 S는 최소 원소 m을 가진다.∀S⊆N,  S≠∅ ⇒ ∃m∈S  s.t. ∀s ∈ S,  m≤s활용나눗셈 정리와 같은 기본 정리를 증명하는 데 사용.3. 합동 (Congruence)정의m≥1인 정수에 대해, 두 정수 a, b가 mod m에서 합동이면:a ≡ b (mod m) ⇔ m ∣ (a−b)..