Paper 2022/1167
META-BTS: Bootstrapping Precision Beyond the Limit
, Seoul National UniversityAbstract
Bootstrapping, which enables the full homomorphic encryption scheme that can perform an infinite number of operations by restoring the modulus of the ciphertext with a small modulus, is an essential step in homomorphic encryption. However, bootstrapping is the most time and memory consuming of all homomorphic operations. As we increase the precision of bootstrapping, a large amount of computational resources is required. Specifically, for any of the previous bootstrap designs, the precision of bootstrapping is limited by rescaling precision. In this paper, we propose a new bootstrapping algorithm of the Cheon-Kim-Kim-Song (CKKS) scheme to use a known bootstrapping algorithm repeatedly, so called { Meta-BTS}. By repeating the original bootstrapping operation twice, one can obtain another bootstrapping with its precision essentially doubled; it can be generalized to be $k$-fold bootstrapping operations for some $k>1$ while the ciphertext size is large enough. Our algorithm overcomes the precision limitation given by the rescale operation.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. CCS 2022
- Keywords
- Fully Homomorphic Encryption CKKS scheme Approximate Boot- strapping High Precision Small parameters
- Contact author(s)
-
youngjin bae @ cryptolab co kr
jhcheon @ snu ac kr
wony0404 @ snu ac kr
jaehyungkim @ cryptolab co kr
taekyung kim @ cryptolab co kr - History
- 2022-09-07: approved
- 2022-09-07: received
- See all versions
- Short URL
- https://ia.cr/2022/1167
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1167,
author = {Youngjin Bae and Jung Hee Cheon and Wonhee Cho and Jaehyung Kim and Taekyung Kim},
title = {META-BTS: Bootstrapping Precision Beyond the Limit},
howpublished = {Cryptology ePrint Archive, Paper 2022/1167},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1167}},
url = {https://eprint.iacr.org/2022/1167}
}
