Paper 2022/1167

META-BTS: Bootstrapping Precision Beyond the Limit

Youngjin Bae, CryptoLab. Inc.
Jung Hee Cheon, Seoul National University, CrytoLab. Inc.
Wonhee Cho, Seoul National University
Jaehyung Kim, CryptoLab. Inc.
Taekyung Kim, CryptoLab. Inc.

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)
Public-key cryptography
Publication info
Published elsewhere. CCS 2022
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
2022-09-07: approved
2022-09-07: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.