Welcome to the resource topic for 2024/1637
Title:
Bootstrapping Small Integers With CKKS
Authors: Youngjin Bae, Jaehyung Kim, Damien Stehlé, Elias Suvanto
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.
ePrint: https://eprint.iacr.org/2024/1637
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .