Homomorphic Multiplication and Encoding

1) 실수(Real) 데이터 인코딩 기본

• 동기: AI 연산엔 실수가 많으니 HE도 실수 처리가 필요.
• 스케일링 인코딩: 충분히 큰 Δ(1 ≪ Δ ≪ q)로 실수 다항식 (m(X))을 정수계수로 올린 뒤 Zq​[X]/(XN+1) 에 넣는다.
  • 예: m(X)=2.3453+0.21345X−1.2345X2, Δ=10^3⇒ Δm=2345+213X−1234X^2 (mod q).

2) (실수 다항식용) Ring-LWE PKE

• KeyGen: a←U(Rq), s←χ, e←χ, b=−a⋅s + e. 공개키 (b,a), 비밀키 s.
• Enc: 잡음 r, e0, e1←χ. u=r⋅b + e0 + Δm, v = r⋅a + e1​. CT=(u,v).
• Dec: u + v⋅s = Δm+e_decrypt​. 최종 복원은 Δ^−1 스케일다운(+반올림).

3) 근사 복호(Approximate Decoding)

• (Δm+e)/Δ=m+(e/Δ).
• Δ가 충분히 크고 잡음이 작으면 근사 오차 내에서 정확히 복원 → CKKS류의 “근사 HE” 개념.

4) 동형 덧셈 & 평문 곱셈

• 덧셈: CT 성분별 합. 잡음은 합쳐짐.
• 평문 곱셈: pˉ​=Δ⋅p. (b,a)↦(pˉb, pˉa).
  • 결과 메시지 스케일이 Δ^2pm으로 제곱됨(스케일 폭증 주의).

5) 동형 곱셈(CT×CT) 핵심 아이디어

• 두 CT (b1,a1),(b2,a2)에 대해 복호식을 곱하면 s2s^2s2항이 생김.
• 중간 형태: (b1b2, b1a2 + a1b2, a1a2) — 세 번째가 s^2에 걸리는 3-튜플 CT.
• 목표: 이를 relinearization(키 스위칭)으로 다시 (b~,a~) (즉 s에 대한 2-성분 CT)로 변환.

6) 키-스위칭(Key-Switching, KS)

• 문제 설정: ct=(b,a)를 키 s1​에서 s2​로 전환하고 Decs2(ct′) ≈ Decs1(ct).
• 직관: as1​을 s2로 암호화한 “평가키(EK)”가 있으면, a에 EK를 “곱하고 나눈다”.
• 노이즈 이슈 & 해결:
  • Encs2(s1)만으론 a⋅e가 커져 실패.
  • 확대 스케일 P ≈ q로 Encs2(Ps1))를 공개(EK). 그 후 나누기-반올림(divide-and-round)로 P^{-1} 효과를 모듈러에서 구현(다중 모듈러스/확장 모듈러스에서 줄여오기).
• 곱셈 relinearization:
  1. b1b2, b1a2 + a1b2​ 계산.
  2. a1a2​에 대해 KSs2→s(⋅) 적용 → (b^,a^).
  3. 합쳐 (b~,a~) = (b1b2 + b^, b1a2 + a1b2 + a^).
  4. 메시지 스케일은 Δ^2m1m2

7) Rescaling(리스케일)

• 곱셈 후 스케일이 Δ2로 커짐 → 기저 모듈러스 감소와 함께 d≈Δ로 나누어Δ′ = Δ2/d≈Δ로 복귀.
• 실제론 모듈러스 체인 q=q0→q1→⋯을 내려가며 divide-and-round 수행.

8) 데이터 인코딩: Coefficient vs Canonical(슬롯 인코딩)

• Coefficient encoding: 계수별 패킹은 덧셈은 의미 있지만 곱셈이 컨볼루션이어서 슬롯별 곱이 아님.
• Canonical embedding(표준 삽입/인코딩):
  • R=Q[X]/(XN+1)의 근 ζi​들( X^N+1의 N개 근; 짝지어진 켤레)을 이용, 복소 슬롯에 값을 채움.
  • 켤레 제약으로 독립 슬롯 수는 N/2. 다항식 덧셈/곱셈 ↔ 슬롯별 덧셈/곱셈이 일대일로 대응 → 벡터 연산에 적합.

9) 루트와 지도(치환)로 만드는 슬롯 연산

• 치환 τ2t+1: f(X)↦f(X2t+1)는 몫환에서 의미 있는 사상.
• 특히 τ5는 슬롯 벡터의 한 칸 좌측 순환(rotate)에 대응(루트 재배열 ζk=e^iπ5k/N 관점).
• τ−1: f(X)↦f(−X^(N−1))=f(X−1)는 복소 켤레(conjugation)에 대응.
• 결론: 회전/복제/켤레 등 슬롯 연산은 적절한 치환+KS(=Galois key)로 실현.

10) 자주 나오는 조건/관계식 체크

• 스케일: 1≪Δ≪q, 곱셈 시 Δ^2≪q 가정.
• KS에서 확대 인자 P ≈ q, divide-and-round로 안정화.
• 곱셈 후 Rescale로 Δ 복귀(+ 모듈러스 레벨 다운).
• 잡음: e_round,e_decrypte​는 항상 Δ에 비해 충분히 작게 유지

11) 미니 연습문제(스스로 점검)

1. Δ=10^3, m(X)=1.23−0.045. Δm mod q를 쓰고, Enc/Dec 과정을 식으로 써보라.
2. 두 CT를 곱했을 때 나오는 3-튜플 형태와, 이를 KS로 2-튜플로 줄이는 단계를 단계별로 정리하라(필요한 평가키 명시).
3. Canonical embedding에서 왜 독립 슬롯이 N/2개인지 켤레 근거로 설명하라.
4. τ5​가 한 칸 좌측 회전이 되는 이유를 루트 지수( 5^k) 관점에서 적어라.

12) 빠른 암기 포인트(한 줄 요약)

• 실수 인코딩은 Δ 스케일 → 덧셈 OK, 곱셈은 스케일 제곱 → relinearization(+KS) → rescale.
• Canonical embedding으로 (N/2) 슬롯 병렬연산, 회전/켤레는 치환+KS(Galois key).
• KS 핵심: P≈q 로 키항을 “키우고” → 나누기-반올림으로 안정화.