Paper 2019/688

Better Bootstrapping for Approximate Homomorphic Encryption

Kyoohyung Han and Dohyeong Ki

Abstract

After Cheon et al. (Asiacrypt' 17) proposed an approximate homomorphic encryption scheme, Heaan, for operations between encrypted real (or complex) numbers, the scheme is widely used in a variety of fields with needs on privacy-preserving in data analysis. After that, a bootstrapping method for Heaan is proposed by Cheon et al. (Eurocrypt' 18) with modulus reduction being replaced by a sine function. In this paper, we generalize the Full-RNS variant of Heaan proposed by Cheon et al. (SAC, 19) to reduce the number of temporary moduli used in key-switching. As a result, our scheme can support more depth computations without bootstrapping while ensuring the same level of security. We also propose a new polynomial approximation method to evaluate a sine function in an encrypted state, which is specialized for the bootstrapping for Heaan. Our method considers a ratio between the size of a plaintext and the size of a ciphertext modulus. Consequently, it requires a smaller number of non-scalar multiplications, which is about half of the Chebyshev method. With our variant of the Full-RNS scheme and a new sine evaluation method, we firstly implement bootstrapping for a Full-RNS variant of approximate homomorphic encryption scheme. Our method enables bootstrapping for a plaintext in the space $\mathbb{C}^{16384}$ to be completed in 52 seconds while preserving 11 bit precision of each slot.

Note: Minor change in comparison subsection of Section 3.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. CT-RSA 2020
Keywords
Homomorphic Encryption and Bootstrapping
Contact author(s)
kyoohyunghan @ gmail com
wooki7098 @ snu ac kr
History
2019-12-05: last of 8 revisions
2019-06-11: received
See all versions
Short URL
https://ia.cr/2019/688
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/688,
      author = {Kyoohyung Han and Dohyeong Ki},
      title = {Better Bootstrapping for Approximate Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/688},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/688}},
      url = {https://eprint.iacr.org/2019/688}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.