International Association for Cryptologic Research

International Association
for Cryptologic Research


Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys

Jean-Philippe Bossuat , EPFL
Christian Mouchet , EPFL
Juan Troncoso-Pastoriza , EPFL
Jean-Pierre Hubaux , EPFL
DOI: 10.1007/978-3-030-77870-5_21 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: We present a bootstrapping procedure for the full-RNS variant of the approximate homomorphic-encryption scheme of Cheon et al., CKKS (Asiacrypt 17, SAC 18). Compared to the previously proposed procedures (Eurocrypt 18 & 19, CT-RSA 20), our bootstrapping procedure is more precise, more efficient (in terms of CPU cost and number of consumed levels), and is more reliable and 128-bit-secure. Unlike the previous approaches, it does not require the use of sparse secret-keys. Therefore, to the best of our knowledge, this is the first procedure that enables a highly efficient and precise bootstrapping with a low probability of failure for parameters that are 128-bit-secure under the most recent attacks on sparse R-LWE secrets. We achieve this efficiency and precision by introducing three novel contributions: (i) We propose a generic algorithm for homomorphic polynomial-evaluation that takes into account the approximate rescaling and is optimal in level consumption. (ii) We optimize the key-switch procedure and propose a new technique for linear transformations (double hoisting). (iii) We propose a systematic approach to parameterize the bootstrapping, including a precise way to assess its failure probability. We implemented our improvements and bootstrapping procedure in the open-source Lattigo library. For example, bootstrapping a plaintext in C^32768 takes 18 seconds, has an output coefficient modulus of 505 bits, a mean precision of 19.1 bits, and a failure probability of 2^-15.58. Hence, we achieve 14.1x improvement in bootstrapped throughput (plaintext-bit per second), with respect to the previous best results, and we have a failure probability 468x smaller and ensure 128-bit security.
Video from EUROCRYPT 2021
  title={Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys},
  author={Jean-Philippe Bossuat and Christian Mouchet and Juan Troncoso-Pastoriza and Jean-Pierre Hubaux},