Batch Bootstrapping for Homomorphic Encryption with Efficient Key Size = 경량화된 연산키를 가지는 동형암호 일괄 재부팅 기법에 관한 연구

국문 초록 (Abstract)

Cheon–Kim–Kim–Song (CKKS) 동형암호는 자원이 사용자가 실수 혹은 복소수에 대한 연산을 계산 능력이 뛰어난 서버에 안전하게 위탁할 수 있게 한다. 동형암호에서 임의의 깊이를 갖는 회로를 평가하기 위해서는 재부팅 (bootstrapping)을 수행해야 하는데 재부팅 알고리즘은 동형암호체계에서 가장 무거운 연산 중 하나이며, 클라이언트가 수 GB에 달하는 연산키를 생성하여 서버로 전송해야 한다. 따라서 동형암호의 효율성을 저해하지 않으면서 (1) 재부팅을 가속하고 (2) 연산키의 크기를 줄이는 것이 매우 중요하다.

본 학위논문에서는 효율성을 유지하면서도 재부팅을 지원하고, 사용자 측 비용을 줄이는 두 가지 새로운 키 관리 시스템인 KG+와 BTS+를 제안한다. 제안하는 시스템은 키 전송을 위한 파라미터와 동형연산에 사용되는 연산키의 파라미터를 분리하는 새로운 환 변환 기법 (ring-switching)에 기반한다. 즉, 사용자는 크기 측면에서 최적인 파라미터로 생성한 가벼운 전송키 (transmission key)를 서버에 전송하고, 서버는 이를 바탕으로 계산에 최적인 파라미터의 연산키 (evaluation key)를 연산을 통해 획득한다. Lee-Lee-Kim-No [Asiacrypt'23]의 키 관리 시스템과 비교했을 때, KG+는 동형연산 성능을 저하시키지 않으면서 연산키의 크기를 크게 줄이며, BTS+는 동형연산의 세밀도(granularity)를 일부 희생하는 대신 연산키 크기를 추가로 감소시킨다.

이어서 CKKS 에서의 일괄 재부팅 (batch bootstrapping)을 가속하는 새로운 알고리즘들을 제시한다. 동형암호에서의 환의 차원인 N에 대하여, SlotToCoeff와 CoeffToSlot 단계는 이산 푸리에 변환 (DFT)과 역과정 (iDFT)을 동형적으로 적용하는 평문 행렬과 암호문 행렬간의 곱셈 (PCMM)으로 볼 수 있으며, 이때 평문행렬로는 이산 푸리에 변환 행렬 및 그 역행렬이 사용된다. 이들 중 CoeffToSlot은 가장 큰 암호문 모듈러스 (modulus) 에서 다수의 키변환(key-switching) 연산을 수행하므로 특히 비용이 크다.

본 논문에서는 이산 푸리에 역변환 행렬이 유도하는 PCMM 연산을, 매우 큰 암호문 모듈러스에서 수행할 필요 없이 작은 크기의 정수 행렬에 대한 PCMM으로 재구성할 수 있음을 보인다. Bae et al. [Crypto’24]의 방법론을 기반으로, 일괄 CoeffToSlot 단계를 이산 푸리에 역변환 행렬에 대한 평문 상에서의 일괄 이산 푸리에 역변환 연산으로 환원하고, 이를 고속 푸리에 변환 (FFT)을 활용하여 전체 계산량을 O(N^2 logN)으로 달성한다. 이 과정은 암호문 레벨 (level)을 소모하지 않으며, 하나의 암호문 당 단 한 번의 키변환 연산만을 요구한다. 또한 Cheon et al. [ePrint’25]이 제안한 Slots-in-Coefficient (SinC) 인코딩 (encoding) 을 활용하여, N 이하의 임의의 배치 크기 d를 지원하도록 알고리즘을 일반화한다.

마지막으로 KG+와 BTS+를 다양한 CKKS FHE 파라미터에 대해 구현하고 실험 결과를 제시한다. 환의 치원 N이 65,536 인 CKKS 재부팅에서 전송키의 크기는 KG+ 가 325-609 MB, BTS+가 285 MB이며, 이는 각각 Lee–Lee–Kim–No 대비 3.09-4.37배, 3.51-9.30배 더 감소했다. 또한 제안한 일괄 재부팅 알고리즘에 대해, 배치 크기 N과 N 이하의 일반적인 배치 크기 d을 모두를 고려한 실험 결과를 제시한다. 배치 크기가 N인 경우 환의 차원이 N = 16,384 인 새로운 동형암호 파라미터를 제안하고, 단일 스레드 CPU에서 암호문 하나 당 재부팅에 걸리는 시간을 0.213 초로 달성했다. 추가로 환의 차원이 $N = 2^{15}$에서 가 $32$부터 $512$까지 다양한 배치 크기에 대한 일괄 재부팅을 구현했다. 이때 암호문 하나 당 재부팅이 각각 2.385 초 및 1.697 초가 소요됨을 보였으며, 이는 기존 파라미터의 $2.69\,$s에서 각각 1.13배 및 1.59배만큼 가속화된 수치이다.

다국어 초록 (Multilingual Abstract)

The Cheon–Kim–Kim–Song (CKKS) fully homomorphic encryption (FHE) scheme enables clients with resource-constrained devices to securely outsource computations over complex numbers to powerful servers. To evaluate circuits of arbitrary depth, one must perform bootstrapping. However, state-of-the-art bootstrapping algorithms incur significant latency and require the client to generate and transmit several gigabytes of FHE keys to the server. It is therefore highly desirable to (1) accelerate bootstrapping and (2) reduce the size of the FHE keys without compromising efficiency.

In this thesis, we propose two novel key management systems, KG+ and BTS+, which reduce the client-side cost of FHE while supporting bootstrapping without compromising efficiency. Our systems rely on a new ring-switching technique that decouples the parameters of keys used for transmission and computation: the client sends compact “transmission keys’’ under size-optimal parameters, and the server derives “evaluation keys’’ under computation-optimal parameters. Compared to the state-of-the-art key management system by Lee et al [Asiacrypt'23], KG+ substantially reduces the key size without degrading homomorphic performance, while BTS+ further shrinks the key size at the cost of reduced granularity in homomorphic computation.

We then introduce novel algorithms to accelerate CKKS bootstrapping in a batched setting. For ring dimension N, the SlotToCoeff and CoeffToSlot steps can be viewed as plaintext–ciphertext matrix multiplications (PCMMs) that homomorphically apply the discrete Fourier transform (DFT) and its inverse (iDFT), using the DFT matrix and its inverse as plaintext matrices; among these, \textsf{CoeffToSlot} is particularly expensive because it performs numerous key-switching operations at the largest ciphertext modulus.

We show that the PCMM induced by the inverse DFT matrix can be reformulated as a PCMM over a small integer matrix, without resorting to extremely large ciphertext moduli. Building on the methodology of Bae et al. [Crypto’24], we reduce this CPMM to cleartext matrix multiplications by the inverse DFT matrix, achieving an overall computational cost of O(N^2 log N) by leveraging the fast Fourier transform (FFT), without consuming levels and while requiring, in an amortized sense, only a single key-switching operation per ciphertext. Moreover, we generalize the algorithm to support an arbitrary batch size d (less than N) by leveraging the Slots-in-Coefficient (SinC) encoding proposed by Cheon et al. [ePrint’25].

Finally, We provide implementations for both KG+ and BTS+ for various CKKS FHE parameters. The transmission key sizes for CKKS bootstrapping with ring dimension 65,536 are 325-609 MB for KG+ and 285 MB for BTS+. These are 3.09-4.37 times and 3.51-9.30 times smaller than Lee-Lee-Kim-No, respectively.
We also present experimental results for our batch bootstrapping algorithm, considering both the full batch size $N$ and flexible batch sizes d less than N. For full-batch bootstrapping, we propose a novel FHE parameter with ring degree N = 16,384, achieving an amortized runtime of 0.213 second on a single-threaded CPU. In addition, we demonstrate flexible-batch bootstrapping with batch sizes ranging from 32 to 512 using a ring degree of N = 32,768. The amortized bootstrapping times for batch sizes 32 and 512 are 2.385 s and 1.697 s, respectively, which correspond to 1.13 times and 1.59 times speedups over the bootstrapping time of the original parameter set.

목차 (Table of Contents)

• Abstract 1
• 1 Introduction 5
• 1.1 Contributions 7
• 1.2 Technical Overview 8
• 1.2.1 Lightweight Key Management Systems 8
• 1.2.2 Fast Batch Bootstrapping 12
• 1.3 List of Papers 15
• 2 Preliminary 16
• 2.1 Notation 16
• 2.2 Mathematical Backgrounds 17
• 2.2.1 Discrete Fourier Transform 17
• 2.2.2 Galois Automorphisms and Trace 18
• 2.2.3 Module Homomorphism and Toeplitz Matrix 19
• 2.2.4 Decomposition of the DFT matrix 20
• 2.3 Homomorphic Encryption 21
• 2.3.1 Encoding methods with bit-reversed order 21
• 2.3.2 RNS-based Gadget Decomposition and Key Switching 22
• 2.3.3 Ring-switching Technique 23
• 2.3.4 Bootstrapping and Homomorphic DFT 24
• 2.3.5 Matrix Encryption and Homomorphic Transpose 25
• 2.3.6 CKKS Parameters and Key Size 26
• 2.3.7 Hierarchical Rotation Key System 28
• 3 Lightweight Bootstrapping via Key Size Reduction 30
• 3.1 Key Generation over Extension Ring 30
• 3.1.1 Ring-switching for HE keys 31
• 3.1.2 Key-switching Key Generation over Extension Ring 33
• 3.1.3 Rotation Key Generation over Extension Ring 35
• 3.2 Key Management Systems 37
• 3.2.1 KG+ Key Management System 37
• 3.2.2 BTS+ Key Management System 39
• 4 Fast Batch Bootstrapping for CKKS 42
• 4.1 Homomorphic Linear Transformation 42
• 4.2 Homomorphic DFT with Matrix Multiplication 43
• 4.3 Fast Batch CoeffToSlot for Bootstrapping 44
• 4.4 Overall Procedure of Batch Bootstrapping 47
• 5 Fast CKKS Boostrapping with Flexible Batch 49
• 5.1 SinC encoding, revisited 49
• 5.2 Application to homomorphic DFT with flexible batch 52
• 5.3 Fast SinC-encoding Conversion and Application to SinCBoot 54
• 6 Experimental Results 57
• 6.1 Implementations for KG+ and BTS+ 57
• 6.1.1 Parameter Settings 57
• 6.1.2 Key Generation for ResNet-20 Models 59
• 6.1.3 Key Generation for Bootstrapping 60
• 6.2 Implementations for Batch Bootstrapping 61
• 6.2.1 FHE Parameters 61
• 6.2.2 Experimental Results 62
• Bibliography 64
• Abstract (in Korean) 68
• Acknowledgement 70