Paper 2021/691
General Bootstrapping Approach for RLWE-based Homomorphic Encryption
Andrey Kim, Maxim Deryabin, Jieun Eom, Rakyong Choi, Yongwoo Lee, 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.
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
-
CC BY
BibTeX
@misc{cryptoeprint:2021/691,
author = {Andrey Kim and Maxim Deryabin and Jieun Eom and Rakyong Choi and Yongwoo Lee and Whan Ghang and Donghoon Yoo},
title = {General Bootstrapping Approach for {RLWE}-based Homomorphic Encryption},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/691},
year = {2021},
url = {https://eprint.iacr.org/2021/691}
}
