You are looking at a specific version 20201008:204443 of this paper. See the latest version.

Paper 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.

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Fully Homomorphic EncryptionBootstrappingImplementation
Contact author(s)
jean-Philippe bossuat @ epfl ch
christian mouchet @ epfl ch
juan troncoso-pastoriza @ epfl ch
jean-pierre hubaux @ epfl ch
History
2022-08-26: last of 5 revisions
2020-10-06: received
See all versions
Short URL
https://ia.cr/2020/1203
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.