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, \(\textsf{SI} \text {-}\textsf{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. \(\textsf{SI} \text {-}\textsf{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 \(\textsf{SI} \text {-}\textsf{BTS} \) to simultaneously bootstrap multiple CKKS ciphertexts for bits. The resulting \(\textsf{BB} \text {-}\textsf{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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Bootstrapping Small Integers With CKKS

  • Youngjin Bae,
  • Jaehyung Kim,
  • Damien Stehlé,
  • Elias Suvanto

摘要

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, \(\textsf{SI} \text {-}\textsf{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. \(\textsf{SI} \text {-}\textsf{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 \(\textsf{SI} \text {-}\textsf{BTS} \) to simultaneously bootstrap multiple CKKS ciphertexts for bits. The resulting \(\textsf{BB} \text {-}\textsf{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.