Paper 2021/691
General Bootstrapping Approach for RLWE-based Homomorphic Encryption
Andrey Kim and Maxim Deryabin and Jieun Eom and Rakyong Choi and Yongwoo Lee and Whan Ghang and Donghoon Yoo
Abstract
An approximate homomorphic encryption scheme called CKKS (Cheon-Kim-Kim-Song) is considered one of the most promising fully homomorphic encryption (FHE) schemes since it enables computations on real and complex numbers in encrypted form. Several bootstrapping approaches were proposed for CKKS to refresh a modulus in a ciphertext. However all the existing bootstrapping approaches for CKKS rely on polynomial approximation of a modular reduction function and consequently the quality of a message deteriorates due to errors produced by the polynomial approximation. Also, the polynomial approximation usually consumes a huge number of multiplicative levels. We propose the first bootstrapping approach for the CKKS scheme without polynomial approximation on the modular reduction function. Instead, we adopt a blind rotation technique from FHEW-type schemes and as a result our approach introduces an error which is comparable to a rescaling error while consuming only one multiplicative level. We demonstrate that our bootstrapping procedure can be generalized to the BGV and BFV schemes with minor modifications in the proposed algorithms. We also present several optimizations including a compact representation of public keys required for bootstrapping and a modified blind rotation technique for the case of sparse secret key.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- BootstrappingFully Homomorphic Encryption
- Contact author(s)
-
andrey kim @ samsung com
max deriabin @ samsung com
jieun eom @ samsung com
rakyong choi @ samsung com
yw0803 lee @ samsung com
whan ghang @ samsung com
say yoo @ samsung com - History
- 2021-10-15: last of 2 revisions
- 2021-05-28: received
- See all versions
- Short URL
- https://ia.cr/2021/691
- License
-
CC BY