You are looking at a specific version 20210714:010959 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.