Paper 2022/1167 Original: eprint.iacr.org/2022/1167 ↗

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.