Paper 2018/153

Bootstrapping for Approximate Homomorphic Encryption

Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song


This paper extends the leveled homomorphic encryption scheme for an approximate arithmetic of Cheon et al. (ASIACRYPT 2017) to a fully homomorphic encryption, i.e., we propose a new technique to refresh low-level ciphertexts based on Gentry's bootstrapping procedure. The modular reduction operation is the main bottleneck in the homomorphic evaluation of the decryption circuit. We exploit a scaled sine function as an approximation of the modular reduction operation and present an efficient evaluation strategy. Our method requires only one homomorphic multiplication for each of iterations and so the total computation cost grows linearly with the depth of the decryption circuit. We also show how to recrypt packed ciphertexts on the RLWE construction with an open-source implementation. For example, it takes 139.8 seconds to refresh a ciphertext that encrypts 128 numbers with 12 bits of precision, yielding an amortized rate of 1.1 seconds per slot.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2018
Homomorphic encryptionapproximate arithmeticbootstrapping
Contact author(s)
lucius05 @ snu ac kr
2018-02-11: received
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Kyoohyung Han and Andrey Kim and Miran Kim and Yongsoo Song},
      title = {Bootstrapping for Approximate Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2018/153},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.