Cryptology ePrint Archive: Report 2020/1203

Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys

Jean-Philippe Bossuat and Christian Mouchet and Juan Troncoso-Pastoriza and Jean-Pierre Hubaux

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 both more precise and more efficient, in terms of CPU cost and number of consumed levels. 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 for parameters that are 128-bit-secure under more recent attacks on sparse R-LWE secrets.

We achieve this by introducing two novel contributions applicable to the CKKS scheme: (i) We propose a generic algorithm for homomorphic polynomial-evaluation that is scale-invariant and optimal in level consumption. (ii) We optimize the key-switch procedure and propose a new technique for performing rotations (\textit{double hoisting}); it significantly reduces the complexity of homomorphic matrix-vector products.

Our scheme improvements and bootstrapping procedure are implemented in the open-source Lattigo library. For example, bootstrapping a plaintext in $\mathbb{C}^{32768}$ takes 17 seconds, with an output coefficient modulus of 505 bits and a mean precision of 19.2 bits. Thus, we achieve an order of magnitude improvement in bootstrapped throughput (plaintext-bit per second) with respect to the previous best results, while ensuring 128-bit of security.

Category / Keywords: public-key cryptography / Fully Homomorphic Encryption, Bootstrapping, Implementation

Date: received 1 Oct 2020, last revised 8 Oct 2020

Contact author: jean-Philippe bossuat at epfl ch, christian mouchet@epfl ch, juan troncoso-pastoriza@epfl ch, jean-pierre hubaux@epfl ch

Available format(s): PDF | BibTeX Citation

Note: Phrasing and English grammar revision of the whole paper. The technical part and evaluation parts remain unchanged.

Version: 20201008:204443 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]