### META-BTS: Bootstrapping Precision Beyond the Limit

##### Abstract

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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/1167

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.