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 .