Paper 2022/024

Bootstrapping for Approximate Homomorphic Encryption with Negligible Failure-Probability by Using Sparse-Secret Encapsulation

Jean-Philippe Bossuat, Tune Insight SA
Juan Ramón Troncoso-Pastoriza, Tune Insight SA
Jean-Pierre Hubaux, École Polytechnique Fédérale de Lausanne

Bootstrapping parameters for the approximate homomorphic-encryption scheme of Cheon et al., CKKS (Asiacrypt 17), are usually instantiated using sparse secrets to be efficient. However, using sparse secrets constrains the range of practical parameters within a tight interval, as they must support a large enough depth for the bootstrapping circuit but also be secure with respect to the sparsity of their secret. We present a bootstrapping procedure for the CKKS scheme that combines both dense and sparse secrets. Our construction enables the use of parameters for which the homomorphic capacity is based on a dense secret, yet with a bootstrapping complexity that remains the one of a sparse secret and with a large security margin. Moreover, this also enables us to easily parameterize the bootstrapping circuit so that it has a negligible failure probability that, to the best of our knowledge, has never been achieved for the CKKS scheme. When using the parameters of previous works, our bootstrapping procedures enables a faster procedure with an increased precision and lower failure probability. For example we are able to bootstrapp a plaintext of $\mathbb{C}^{32768}$ in 20.2 sec, with 32.11 bits of precision, 285 bits of modulus remaining, a failure probability of $2^{-138.7}$ and 128 bit security.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. ACNS 2022
Fully Homomorphic EncryptionBootstrappingImplementation
Contact author(s)
jean-philippe @ tuneinsight com
2023-04-03: last of 3 revisions
2022-01-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jean-Philippe Bossuat and Juan Ramón Troncoso-Pastoriza and Jean-Pierre Hubaux},
      title = {Bootstrapping for Approximate Homomorphic Encryption with Negligible Failure-Probability by Using Sparse-Secret Encapsulation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/024},
      year = {2022},
      doi = {10.1007/978-3-031-09234-3_26},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.