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)
- 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
-
CC BY