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: We propose a new bootstrapping approach that works for all three Brakerski-Gentry-Vaikuntanathan (BGV), Brakerski/Fan-Vercauteren (BFV), and Cheon-Kim-Kim-Song (CKKS) schemes. This approach adopts a blind rotation technique from FHEW-type schemes. For BGV and BFV, our bootstrapping does not have any restrictions on plaintext modulus unlike typical cases of the previous methods. For CKKS, our approach introduces an error comparable to a rescaling error which enables more than 70 bits of precision after bootstrapping while consuming only 1-2 levels. Due to the high precision of the proposed bootstrapping algorithm, it is the first bootstrapping resistant to the security vulnerability of CKKS found by Li and Micciancio (Eurocrypt 2021). In addition, we introduce methods to reduce the size of public keys required for blind rotations generated by a secret key holder.

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

Date: received 26 May 2021, last revised 15 Oct 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: 20211015:073818 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]