High-Precision Bootstrapping for Approximate Homomorphic Encryption by Error Variance Minimization

Yongwoo Lee; Joon-Woo Lee; Young-Sik Kim; Yongjune Kim; Jong-Seon No; HyungChul Kang

Paper 2020/1549

High-Precision Bootstrapping for Approximate Homomorphic Encryption by Error Variance Minimization

Yongwoo Lee, Joon-Woo Lee, Young-Sik Kim, Yongjune Kim, Jong-Seon No, and HyungChul Kang

Abstract

The Cheon-Kim-Kim-Song (CKKS) scheme (Asiacrypt'17) is one of the most promising homomorphic encryption (HE) schemes as it enables privacy-preserving computing over real (or complex) numbers. It is known that bootstrapping is the most challenging part of the CKKS scheme. Further, homomorphic evaluation of modular reduction is the core of the CKKS bootstrapping, but as modular reduction is not represented by the addition and multiplication of complex numbers, approximate polynomials for modular reduction should be used. The best-known techniques (Eurocrypt'21) use a polynomial approximation for trigonometric functions and their composition. However, all the previous methods are based on an indirect approximation, and thus it requires lots of multiplicative depth to achieve high accuracy. This paper proposes a direct polynomial approximation of modular reduction for CKKS bootstrapping, which is optimal in error variance and depth. Further, we propose an efficient algorithm, namely the lazy baby-step giant-step (BSGS) algorithm, to homomorphically evaluate the approximate polynomial, utilizing the lazy relinearization/rescaling technique. The lazy-BSGS reduces the computational complexity by half compared to the ordinary BSGS algorithm. The performance improvement for the CKKS scheme by the proposed algorithm is verified by implementation over HE libraries. The implementation results show that the proposed method has a multiplicative depth of 10 for modular reduction to achieve state-of-the-art accuracy, while the previous methods have depths of 11 to 12. Moreover, we achieve higher accuracies within a small multiplicative depth, for example, 93-bit within multiplicative depth 11.

Note: Error variance-minimizing approximation is improved (high precision achieved), and the new lazy-BSGS algorithm is proposed.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in EUROCRYPT 2022
Keywords: Bootstrapping Cheon-Kim-Kim-Song (CKKS) scheme Fully homomorphic encryption (FHE)Privacy-preserving machine learning (PPML)Signal-to-noise ratio (SNR).
Contact author(s): yw0803 lee @ samsung com
joonwoo3511 @ ccl snu ac kr
iamyskim @ chosun ac kr
yjk @ dgist ac kr
jsno @ snu ac kr
hc1803 kang @ samsung com
History: 2022-02-28: last of 3 revisions; 2020-12-13: received; See all versions
Short URL: https://ia.cr/2020/1549
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1549,
      author = {Yongwoo Lee and Joon-Woo Lee and Young-Sik Kim and Yongjune Kim and Jong-Seon No and HyungChul Kang},
      title = {High-Precision Bootstrapping for Approximate Homomorphic Encryption by Error Variance Minimization},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1549},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1549}},
      url = {https://eprint.iacr.org/2020/1549}
}