Homomorphic Multiplication and Encoding

1. Real Number Operations

• AI에서는 정수보다 실수 연산이 더 많이 사용됨.
• 따라서 암호화도 실수 데이터를 다룰 수 있어야 함.
• Fixed-point encoding 방식 활용 (스케일링).

---

2. Encoding for Real-Coefficient Polynomials

• 기본 Ring-LWE 암호화는 비트 벡터만 처리 가능.
• 실계수 다항식을 처리하기 위해 스케일링 인자 Δ 사용.
  
  • m∈Q[X]/(XN+1) → Δm∈Zq​[X]/(XN+1)
• 조건: 1≪Δ≪q.

---

3. Ring-LWE Encryption for Real Polynomials

• KeyGen
  
  • a←U(Rq​), e←χn
  • b=−a⋅s+e.
• Enc
  • c = (u,v) = (r⋅b+e0​+Δm,r⋅a+e1​).
• Dec
  
  • u+v⋅s=Δm+e. 스케일링 Δ−1\Delta^{-1}Δ−1로 원복.

---

4. Approximate Decoding

• 복호화 결과는 m+Δe​.
• 오차가 작으면 올바른 근사치 복구 가능.
• 따라서 “근사 준동형 암호 (Approximate HE)” 라고 부름.

---

5. Homomorphic Addition

• 암호문 단순 합
  
  • (b1​,a1​)⊕(b2​,a2​) = (b1​+b2​, a1​+a2​)
• 복호화
  • Δ(m1​+m2​)+(e1​+e2​).

---

6. Homomorphic Plaintext Multiplication

• 평문 상수 (p)와 곱하기
  
  • (b,a)↦(Δp⋅b,Δp⋅a)
• 결과: Δ^2mp+Δpe.

---

7. Homomorphic Multiplication (Ciphertext × Ciphertext)

• 두 암호문 곱: 복호화 시 Δ2m1m2+noise.
• 문제: 항에 s² 가 등장 → 직접 복호화 불가.
• 해결:
  • 보조 암호문 (ct2) 정의 (s² 관련).
  • Key-Switching 이용 → s² 를 다시 s에 맞는 형태로 변환.
  • Relinearization 과정.

---

8. Key-Switching

• 암호문을 (s_1)에서 (s_2)로 변환.
• Key-Switching Key 필요
  • Encs2​​(Ps1​) 형태로 공개.
  • 연산 시 (P^{-1}) 적용(division with rounding).
• 이를 통해 곱셈 결과에서 나온 (s^2) 항을 다시 (s) 기반 암호문으로 바꿀 수 있음.

---

9. Rescaling

• 곱셈 시 스케일링 인자 Δ가 제곱됨 (Δ → Δ² → Δ⁴ → …).
• 따라서 각 곱셈 후에 다시 Δ로 줄여야 함.
• 방법: 모듈러스 축소 및 divide-and-round.

---

✅ 핵심 요약

• 실수 연산 지원: 스케일링 Δ 사용.
• 근사 복호화: 작은 오류는 무시 가능.
• 덧셈/곱셈: 암호문 조합으로 가능.
• 곱셈 문제: (s^2) 항 발생 → Key-Switching + Relinearization으로 해결.
• Rescaling: 곱셈 후 증가한 Δ를 다시 줄여줌.