Homomorphic Encryption / Ring-LWE

 

1. Homomorphism (동형사상)

• 정의: 두 대수 구조(예: 군, 환, 체) 사이에서 연산을 보존하는 함수.
• 예시
  • f(x)=2x,f:(Z,+)→(Z,+)→ 동형성 성립.
  • f(x)=2x,f:(Z,×)→(Z,×)→ 동형성 불성립.
  • g(x)=ex,g:(R,+)→(R+,×)→ 동형성 성립.

---

2. Homomorphic Encryption (동형암호)

• 아이디어: 평문에서의 연산(+, ×) 결과를 암호문에서도 동일하게 수행할 수 있도록 보장.
  • Dec(Enc(m1) ⊛ Enc(m2)) = m1 ∗ m2
• 비공식 정의: 암호화된 데이터 상태에서 사칙연산, 논리연산을 수행할 수 있는 암호화 기법.
• 공식 정의
  • E=(KeyGen,Enc,Eval,Dec)
  • KeyGen: 키 생성
  • Enc: 평문 → 암호문
  • Eval: 암호문 연산
  • Dec: 암호문 → 평문

---

3. Correctness & Security

• 정확성 (Correctness)
  
  • 복호화했을 때 원래 연산 결과와 다를 확률은 무시할 수 있을 만큼 작아야 함.
• 보안성 (Security):
  • 최소한 IND-CPA (선택평문공격에 대한 안전성)을 만족해야 함.
  • 즉, 공격자가 두 평문 중 어느 것이 암호화되었는지 추측할 확률은 거의 50%를 넘지 않아야함.

---

4. LWE (Learning With Errors) 기반 암호

• LWE 문제: 선형 방정식에 작은 오차(error)를 섞어 비밀 값을 숨기는 문제.
• LPR 암호화 (Lyubashevsky–Peikert–Regev): LWE 기반 대표적인 공개키 암호화 방식.
• 한계: 공개키와 암호문 크기가 너무 큼 → 비효율적.

---

5. Ring-LWE (환 기반 LWE)

• 아이디어: 다항식 환(Quotient Ring) 구조를 이용해 LWE를 최적화.
• 장점:
  • 공개키 크기 감소 (LWE 대비 훨씬 작음).
  • 암호문 크기 감소, 더 많은 비트 저장 가능.
• 보안성: Ring-LWE 문제의 난이도는 격자 문제(SIVP)와 연결되어, 양자컴퓨터 시대에도 안전하다고 여겨짐.

---

6. 발전 흐름

1. LWE 기반 공개키 암호 (LPR)
2. Ring-LWE 기반 공개키 암호 (효율성 ↑)
3. Leveled Homomorphic Encryption (레벨 제한 HE)
4. Fully Homomorphic Encryption (완전 동형암호, Bootstrapping 포함)
5. 응용: 프라이버시 보호 머신러닝, CKKS(근사 연산 지원 HE)

---

핵심 포인트

• 동형사상 → 동형암호로 확장: 암호문 상태에서도 안전하게 연산 가능.
• 보안성은 최소 IND-CPA 필요.
• Ring-LWE는 기존 LWE보다 효율적이고, lattice 기반 보안성을 유지.
• 최신 연구는 머신러닝, 데이터 프라이버시 보호에 활발히 적용 중.

---

👉 이 요약을 시험 대비용 ‘정의 + 성질 + 예시’ 정리표 형태로 다시 만들어 드릴까요, 아니면 시각화 다이어그램(예: 흐름도, 구조도)으로 정리해드릴까요?