International Association for Cryptologic Research

International Association
for Cryptologic Research


Bootstrapping Bits with CKKS

Youngjin Bae , CryptoLab Inc.
Jung Hee Cheon , CryptoLab Inc. / Seoul National University
Jaehyung Kim , CryptoLab Inc.
Damien Stehlé , CryptoLab Inc.
Search ePrint
Search Google
Conference: EUROCRYPT 2024
Abstract: The Cheon-Kim-Kim-Song (CKKS) fully homomorphic encryption scheme is designed to efficiently perform computations on real numbers in an encrypted state. Recently, Drucker et al [J. Cryptol.] proposed an efficient strategy to use CKKS in a black-box manner to perform computations on binary data. In this work, we introduce several CKKS bootstrapping algorithms designed specifically for ciphertexts encoding binary data. Crucially, the new CKKS bootstrapping algorithms enable to bootstrap ciphertexts containing the binary data in the most significant bits. First, this allows to decrease the moduli used in bootstrapping, saving a larger share of the modulus budget for non-bootstrapping operations. In particular, we obtain full-slot bootstrapping in ring degree 2^14 for the first time. Second, the ciphertext format is compatible with the one used in the DM/CGGI fully homomorphic encryption schemes. Interestingly, we may combine our CKKS bootstrapping algorithms for bits with the fast ring packing technique from Bae et al [CRYPTO'23]. This leads to a new bootstrapping algorithm for DM/CGGI that outperforms the state-of-the-art approaches when the number of bootstraps to be performed simultaneously is in the low hundreds.
  title={Bootstrapping Bits with CKKS},
  author={Youngjin Bae and Jung Hee Cheon and Jaehyung Kim and Damien Stehlé},