Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

1. 문제 정의 (Problem Statement)

• CKKS 의 한계: 동형 암호 (HE) 의 대표적인 방식인 CKKS 는 실수 근사 연산에 효율적이지만, 본질적으로 덧셈과 곱셈만 지원합니다. 따라서 암호화된 데이터에서 모듈로 (mod) 연산과 같은 비선형이거나 불연속적인 연산을 수행하는 것은 매우 어렵습니다.
• 기존 방법의 부족: 기존 연구들 (예: Lee et al. [LLL+21] 등) 은 사인 (sin) 함수나 역삼각함수를 이용한 다항식 근사를 통해 mod 함수를 구현하려 시도했으나, 이는 입력 도메인의 **일부 구간 (subrange)**에서만 정확한 결과를 내었습니다. 입력 도메인의 전체 구간에서 정확한 근사를 제공하는 해결책은 부재했습니다.
• 데이터 패킹의 비효율: CKKS 는 SIMD(Single Instruction Multiple Data) 를 통해 여러 평문을 하나의 암호문에 담을 수 있지만, 작은 정수 입력 (예: 이미지 데이터, 유전 정보 등) 을 처리할 때 슬롯 (slot) 활용도가 낮고, 암호문 업로드 및 전송 비용이 큰 병목 현상을 일으킵니다.

2. 제안 방법론 (Methodology)

저자들은 CKKS 암호문 내에서 전체 입력 구간에 걸쳐 정확한 mod 함수 근사를 가능하게 하는 새로운 방법론과 이를 활용한 데이터 패킹 기법을 제안합니다.

2.1. 정확한 Mod 함수 근사 (Accurate Mod Approximation)

• 기저 (Basis): 기존 방법들과 달리, 입력을 이산적인 정수 점 $(x, x \mod p)$의 집합으로 간주하고 **체비셰프 급수 (Chebyshev series)**와 **다항식 보간 (Polynomial Interpolation)**을 결합합니다.
• 체비셰프 다항식 활용: 런게 현상 (Runge phenomenon) 을 억제하고 균일 근사 (uniform approximation) 를 최적화하기 위해 체비셰프 다항식 ($T_n(x)$) 을 사용합니다.
• 계수 최적화:
  • 최소 제곱법 (Least Squares) 을 사용하여 체비셰프 계수를 구하며, 해가 여러 개일 경우 $\ell_2$-노름이 최소가 되는 해를 선택하여 CKKS 의 노이즈 증폭을 최소화합니다.
  • 스케일링 인자 ($\delta$): 다항식 계수가 1 을 초과하면 CKKS 연산 중 오차가 급격히 증폭될 수 있으므로, 계수들이 1 미만이 되도록 적절한 스케일링 인자 $\delta$를 동적으로 결정합니다.
  • Paterson–Stockmeyer 알고리즘: 고차 다항식 ($D > B$) 을 효율적으로 평가하기 위해 이 알고리즘을 변형하여 적용합니다.
• 성능: 이 방법은 입력 구간 $[0, B]$ 내의 모든 정수 점에서 높은 정확도 (오차 $10^{-8}$ 수준) 를 보장합니다.

2.2. 효율적인 데이터 패킹 기법 (Data Packing Schemes)

소형 정수 입력을 위해 제안된 두 가지 패킹 방식은 CKKS 평문 공간의 활용도를 극대화합니다.

1. BitStack:

   • 원리: 이진 표현을 사용하여 여러 데이터를 하나의 큰 정수로 직렬로 쌓는 방식입니다.
   • 언패킹 (Unpacking): 제안된 Homomorphic Mod 연산을 사용하여 $2^{l_i}$로 나눈 나머지 (mod) 를 구함으로써 각 레이어의 데이터를 순차적으로 추출합니다.
   • 특징: 구조가 매우 컴팩트하지만, 순차적 언패킹으로 인해 곱셈 깊이 (multiplicative depth) 가 많이 소모됩니다.

2. CRTStack (Chinese Remainder Theorem Stack):

   • 원리: 서로소 (pairwise coprime) 인 모듈로 $P_1, P_2, \dots, P_d$를 사용하여 CRT(중국인의 나머지 정리) 기반의 동시 합동식 시스템을 구성합니다.
   • 언패킹: 각 모듈로 $P_i$에 대한 Homomorphic Mod 연산을 병렬로 수행하여 데이터를 추출합니다.
   • 특징: BitStack 보다 공간 효율은 다소 낮을 수 있으나, 병렬 처리가 가능하여 언패킹 시간이 빠르고 오차 전파가 적습니다.

2.3. 추가 활용 기술

• VecConcat & ImgConcat: CKKS 의 허수부 (imaginary part) 슬롯을 활용하여 실수 데이터를 두 배로 압축하거나, 벡터를 연결하는 기법을 제안합니다.
• 응용: BitStack/CRTStack 은 VecConcat 및 ImgConcat 과 결합하여 유연한 데이터 구조를 만들 수 있습니다.

3. 주요 기여 (Key Contributions)

1. 전체 구간 Mod 근사: 불연속적이고 주기적인 성질을 가진 mod 함수를 CKKS 에서 전체 입력 도메인에 걸쳐 정확하게 근사하는 최초의 체비셰프 기반 다항식 방법을 제안했습니다.
2. 고효율 패킹 기법 (BitStack, CRTStack): 작은 정수 입력을 위한 두 가지 패킹 방식을 설계하여 CKKS 평문 공간 활용도를 극대화하고, 암호문 업로드 및 전송 오버헤드를 획기적으로 줄였습니다.
3. 동형 반올림 (Homomorphic Rounding): 제안된 Mod 근사를 기반으로 $Floor$, $Ceil$, $Round$ 연산을 구현하여 소수점 이하 정수 처리가 가능한 CKKS 연산을 가능하게 했습니다.
4. Secret Share to HE 변환: 기존 비밀분산 (Secret Sharing) 방식의 데이터를 CKKS 암호문으로 변환하는 최초의 완전한 변환 체계를 제시했습니다. 이는 별도의 키 관리나 오프라인 전처리가 필요하지 않습니다.

4. 실험 결과 (Results)

• 근사 정확도: 다항식 차수가 45 이상일 때 평균 절대 오차가 $10^{-8}$ 수준으로 달성되었습니다. 기존 방법 (Lee2021, OpenFHE 내장 방법) 에 비해 전체 구간에서 월등히 높은 정확도를 보였습니다.
• 데이터 패킹 성능:
  • BitStack: 기존 비교 방법 (Switch, Extract) 대비 언패킹 시간이 약 10 초 수준으로 단축되었으며 (기존은 수백 초), 오차는 수 차수 감소했습니다.
  • 전송 비용: 제안된 패킹 기법 (Combine 2) 을 사용하면 일반 CKKS 대비 약 100 배 (2 차수) 감소한 통신 비용 (Traffic) 을 달성했습니다.
  • Transcipher 대비: Rubato(Transcipher 프레임워크) 와 비교 시, 사용자 측 암호화 시간이 단축되었고, 언패킹 속도가 약 1.6 배 빠르며, 오차도 1 차수 더 낮았습니다.
• 응용 성능:
  • Secret Share 변환: 참여자 수가 증가해도 오차는 $10^{-8}$ 수준을 유지하며, 트리 기반 재구성을 통해 다항식 차수를 줄일 수 있으나 연산 횟수 증가로 인해 시간 비용이 더 들 수 있음을 확인했습니다.

5. 의의 및 결론 (Significance and Conclusion)

• CKKS 의 기능 확장: CKKS 가 본래 지원하지 않던 불연속 연산 (Mod) 을 정밀하게 수행할 수 있게 함으로써, 암호화된 데이터 처리의 범위를 확장했습니다.
• 실용성 증대: IoT 기기, 스마트 홈, 의료 모니터링 등 대역폭과 계산 자원이 제한된 환경에서 암호화된 데이터의 업로드 및 처리 효율을 크게 향상시켰습니다.
• 보안 프로토콜 통합: 비밀분산 (Secret Sharing) 과 동형 암호 (HE) 간의 간극을 메우는 변환 기법을 제공하여, 하이브리드 보안 시스템 구축에 새로운 가능성을 열었습니다.
• 한계와 전망: 현재 제안된 방법은 입력 범위가 작은 정수 (수십~수백 단위) 에 국한되지만, 이는 유전 정보, 이미지 데이터 등 실제 프라이버시 보호 컴퓨팅에서 빈번하게 등장하는 데이터 유형에 적합하며, 향후 더 큰 범위로 확장 가능한 연구의 토대를 마련했습니다.

이 논문은 CKKS 기반 동형 암호 시스템의 실용적 장벽을 낮추고, 효율적인 데이터 패킹 및 복잡한 연산 수행을 가능하게 하는 중요한 기술적 진전을 이루었습니다.