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 the modulus in a ciphertext. However all the existing bootstrapping approaches for CKKS rely on polynomial approximation of modulus reduction function and consequently, the quality of the message deteriorates due to polynomial approximation errors. We propose the first bootstrapping approach for the CKKS scheme without polynomial approximation of the modulus reduction function. Instead, our procedure adopts blind rotation technique from FHEW-type schemes and as a result, our approach introduces only an error that is comparable to a rescaling error. We also present several optimizations including compact representation of public keys required for bootstrapping and modified blind rotation technique for the case of sparse secret key. We demonstrate that our bootstrapping procedure can be generalized to the BGV and BFV schemes with minor modifications in the proposed algorithms.