Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys

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 (\emph{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 $\mathbb{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.1$\times$ improvement in bootstrapped throughput (plaintext-bit per second), with respect to the previous best results, and we have a failure probability 468$\times$ smaller and ensure 128-bit security.

Note: Updated authors contacts

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2021
Keywords
Fully Homomorphic Encryption Bootstrapping Implementation
Contact author(s)
jean-philippe @ tuneinsight ch
christian mouchet @ epfl ch
juan @ tuneinsight com
jean-pierre hubaux @ epfl ch
History
2022-08-26: last of 5 revisions
See all versions
Short URL
https://ia.cr/2020/1203

CC BY

BibTeX

@misc{cryptoeprint:2020/1203,
author = {Jean-Philippe Bossuat and Christian Mouchet and Juan Troncoso-Pastoriza and Jean-Pierre Hubaux},
title = {Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys},
howpublished = {Cryptology ePrint Archive, Paper 2020/1203},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1203}},
url = {https://eprint.iacr.org/2020/1203}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.