Cryptology ePrint Archive: Report 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.

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

Date: received 26 May 2021, last revised 13 Jul 2021

Contact author: andrey kim at samsung com, max deriabin at samsung com, jieun eom at samsung com, rakyong choi at samsung com, yw0803 lee at samsung com, whan ghang at samsung com, say yoo at samsung com

Available format(s): PDF | BibTeX Citation

Version: 20210714:010959 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]