### High-Precision Bootstrapping of RNS-CKKS Homomorphic Encryption Using Optimal Minimax Polynomial Approximation and Inverse Sine Function

Joon-Woo Lee, Eunsang Lee, Yongwoo Lee, Young-Sik Kim, and Jong-Seon No

##### Abstract

Approximate homomorphic encryption with the residue number system (RNS), called RNS-variant Cheon-Kim-Kim-Song (RNS-CKKS) scheme, is a fully homomorphic encryption scheme that supports arithmetic operations for real or complex number data encrypted. Although the RNS-CKKS scheme is a fully homomorphic encryption scheme, most of the applications with the RNS-CKKS scheme use it as the only leveled homomorphic encryption scheme because of the lack of the practicality of the bootstrapping operation of the RNS-CKKS scheme. One of the crucial problems of the bootstrapping operation is its poor precision. While other basic homomorphic operations ensure sufficiently high precision for practical use, the bootstrapping operation only supports about 20-bit fixed-point precision at best, which is not high precision enough to be used for the reliable large-depth homomorphic computations until now. In this paper, we improve the message precision in the bootstrapping operation of the RNS-CKKS scheme. Since the homomorphic modular reduction process is one of the most important steps in determining the precision of the bootstrapping, we focus on the homomorphic modular reduction process. Firstly, we propose a fast algorithm of obtaining the optimal minimax approximate polynomial of modular reduction function and the scaled sine/cosine function over the union of the approximation regions, called an improved multi-interval Remez algorithm. In fact, this algorithm derives the optimal minimax approximate polynomial of any continuous functions over any union of the finite number of intervals. Next, we propose the composite function method using the inverse sine function to reduce the difference between the scaling factor used in the bootstrapping and the default scaling factor. With these methods, we reduce the approximation error in the bootstrapping of the RNS-CKKS scheme by 1/1176~1/42 (5.4~10.2-bit precision improvement) for each parameter setting. While the bootstrapping without the composite function method has 27.2~30.3-bit precision at maximum, the bootstrapping with the composite function method has 32.6~40.5-bit precision.

Note: We focus on the improvement of the message precision of the RNS-CKKS scheme using our techniques in previous versions of this paper. Simulation results for the message precision of the RNS-CKKS scheme are added in this version.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
Keywords
Approximate homomorphic encryptionBootstrappingComposite function approximationFully homomorphic encryption (FHE)Improved multi-interval Remez algorithmInverse sine functionMinimax approximate polynomial
Contact author(s)
joonwoo3511 @ ccl snu ac kr
eslee3209 @ ccl snu ac kr
yongwool @ ccl snu ac kr
iamyskim @ chosun ac kr
jsno @ snu ac kr
History
2021-07-22: last of 4 revisions
See all versions
Short URL
https://ia.cr/2020/552

CC BY

BibTeX

@misc{cryptoeprint:2020/552,
author = {Joon-Woo Lee and Eunsang Lee and Yongwoo Lee and Young-Sik Kim and Jong-Seon No},
title = {High-Precision Bootstrapping of RNS-CKKS Homomorphic Encryption Using Optimal Minimax Polynomial Approximation and Inverse Sine Function},
howpublished = {Cryptology ePrint Archive, Paper 2020/552},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/552}},
url = {https://eprint.iacr.org/2020/552}
}

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