박사논문심사
김한나
27동 220호
0
288
2025.11.04 15:58
| 구분 | 박사학위 논문 발표 |
|---|---|
| 일정 | 2025-12-09 15:00 ~ 18:00 |
| 강연자 | 강민식 (서울대학교) |
| 기타 | |
| 담당교수 | 천정희 |
시간: 12/9 (화) 오후 4시 ~ 5시
장소: 서울대학교 27동 220호
제목: Batch Bootstrapping for Homomorphic Encryption with Efficient Key Size
(경량화된 연산키를 가지는 동형암호 일괄 재부팅 기법에 관한 연구)
(경량화된 연산키를 가지는 동형암호 일괄 재부팅 기법에 관한 연구)
초록:
The Cheon-Kim-Kim-Song (CKKS) fully homomorphic encryption (FHE) scheme enables clients with resource-constrained devices to securely outsource approximate computations over complex numbers to powerful servers. However, state-of-the-art CKKS bootstrapping still suffers from high latency and requires the client to generate and transmit several gigabytes of evaluation keys, creating substantial computational, communication, and storage overhead. It is therefore crucial to both accelerate bootstrapping and reduce the client-side key footprint without sacrificing throughput.
Our first contribution is a pair of key-management systems, KG+ and BTS+, that reduce the size of FHE transmission keys while supporting high-throughput bootstrapping. Using a new ring-switching technique, we decouple the parameters of keys used for transmission and computation: the client uploads compact ``transmission keys'' under size-optimal parameters, and the server derives ``evaluation keys'' under computation-optimal parameters. Compared to the hierarchical key system of Lee et al. (Asiacrypt 2023), KG+ substantially shrinks the client key size without degrading homomorphic performance, while BTS+ further reduces the key size at the cost of coarser granularity in the supported homomorphic operations.
Our second contribution is a family of algorithms for batched CKKS bootstrapping that accelerate the SlotToCoeff and CoeffToSlot steps. We reinterpret these as plaintext-ciphertext matrix multiplications (PCMMs) by the DFT and inverse DFT matrices, and show that the PCMM induced by the inverse DFT can be reformulated over a small-integer matrix without resorting to large ciphertext moduli. Building on the methodology of Bae et al. (Crypto 2024), we reduce this PCMM to cleartext matrix multiplications and apply FFT to obtain an O(N^2 log N) algorithm that does not consume levels and, amortized, requires only one key-switch per ciphertext. We further generalize the construction to arbitrary batch size d < N using the Slots-in-Coefficient (SinC) encoding of Cheon et al. (ePrint~2025), and show how to instantiate KG+ within our batched bootstrapping framework in both key-precomputation and on-the-fly key-generation regimes.
Our first contribution is a pair of key-management systems, KG+ and BTS+, that reduce the size of FHE transmission keys while supporting high-throughput bootstrapping. Using a new ring-switching technique, we decouple the parameters of keys used for transmission and computation: the client uploads compact ``transmission keys'' under size-optimal parameters, and the server derives ``evaluation keys'' under computation-optimal parameters. Compared to the hierarchical key system of Lee et al. (Asiacrypt 2023), KG+ substantially shrinks the client key size without degrading homomorphic performance, while BTS+ further reduces the key size at the cost of coarser granularity in the supported homomorphic operations.
Our second contribution is a family of algorithms for batched CKKS bootstrapping that accelerate the SlotToCoeff and CoeffToSlot steps. We reinterpret these as plaintext-ciphertext matrix multiplications (PCMMs) by the DFT and inverse DFT matrices, and show that the PCMM induced by the inverse DFT can be reformulated over a small-integer matrix without resorting to large ciphertext moduli. Building on the methodology of Bae et al. (Crypto 2024), we reduce this PCMM to cleartext matrix multiplications and apply FFT to obtain an O(N^2 log N) algorithm that does not consume levels and, amortized, requires only one key-switch per ciphertext. We further generalize the construction to arbitrary batch size d < N using the Slots-in-Coefficient (SinC) encoding of Cheon et al. (ePrint~2025), and show how to instantiate KG+ within our batched bootstrapping framework in both key-precomputation and on-the-fly key-generation regimes.
