Welcome to the resource topic for 2022/024
Title:
Bootstrapping for Approximate Homomorphic Encryption with Negligible Failure-Probability by Using Sparse-Secret Encapsulation
Authors: Jean-Philippe Bossuat, Juan Ramón Troncoso-Pastoriza, Jean-Pierre Hubaux
Abstract: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.
ePrint: https://eprint.iacr.org/2022/024
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 .