Paper 2024/1637

Bootstrapping Small Integers With CKKS

Abstract

The native plaintexts of the Cheon-Kim-Kim-Song (CKKS) fully homomorphic encryption scheme are vectors of approximations to complex numbers. Drucker et al. [J. Cryptol.'24] have showed how to use CKKS to efficiently perform computations on bits and small bit-length integers, by relying on their canonical embeddings into the complex plane. For small bit-length integers, Chung et al. [IACR eprint'24] recently suggested to rather rely on an embedding into complex roots of unity, to gain numerical stability and efficiency. Both works use CKKS in a black-box manner. Inspired by the design by Bae et al. [Eurocrypt'24] of a dedicated bootstrapping algorithm for ciphertexts encoding bits, we propose a CKKS bootstrapping algorithm, $\mathsf{SI\mbox{-}BTS}$ (small-integer bootstrapping), for ciphertexts encoding small bit-length integers. For this purpose, we build upon the DM/CGGI-to-CKKS conversion algorithm from Boura et al. [J. Math. Cryptol.'20], to bootstrap canonically embedded integers to integers embedded as roots of unity. $\mathsf{SI\mbox{-}BTS}$ allows functional bootstrapping: it can evaluate an arbitrary function of its input while bootstrapping. It may also be used to batch-(functional-)bootstrap multiple DM/CGGI ciphertexts. For example, its amortized cost for evaluating an 8-bit look-up table on $2^{12}$ DM/CGGI ciphertexts is 3.75ms (single-thread CPU, 128-bit security). We adapt $\mathsf{SI\mbox{-}BTS}$ to simultaneously bootstrap multiple CKKS ciphertexts for bits. The resulting $\mathsf{BB\mbox{-}BTS}$ algorithm (batch-bits bootstrapping) allows to decrease the amortized cost of a binary gate evaluation. Compared to Bae et al., it gives a 2.4x speed-up.