Bossuat, Jean-PhilippeTroncoso-Pastoriza, JuanHubaux, Jean-Pierre2022-11-212022-11-212022-11-212022-01-0110.1007/978-3-031-09234-3_26https://infoscience.epfl.ch/handle/20.500.14299/192390WOS:000876727100026Bootstrapping 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 enable a faster execution with an increased precision and lower failure probability. For example, we are able to bootstrap a plaintext of C-32768 in 20.2 s, with 32.11 bits of precision, 285 remaining modulus bits, a failure probability of 2(-138.7), and 128 bit security.Computer Science, Information SystemsComputer Science, Theory & MethodsMathematics, AppliedComputer ScienceMathematicsfully homomorphic encryptionbootstrappingimplementationtext::conference output::conference proceedings::conference paper