Paper 2017/735

Faster Bootstrapping with Multiple Addends

TanPing ZHOU, XiaoYuan YANG, LongFei LIU, Wei ZHANG, and YiTao DING


As an important cryptographic primitive in cloud computing and outsourced computation, fully homomorphic encryption (FHE) is an animated area of modern cryptography. However, the efficiency of FHE has been a bottleneck that impeding its application. According to Gentry’s blueprint, bootstrapping, which is used to decrease ciphertext errors, is the most important process in FHE. However, bootstrapping is also the most expensive process that affecting the efficiency of the whole system. Firstly, we notice that, hundreds of serial homomorphic additions take most of the time of bootstrapping. We made use of the properties of Boolean circuit to reduce the number of serial homomorphic additions by two-thirds, and thus constructed an efficient FHE scheme with bootstrapping in 10ms. Secondly, the most expensive parts in our bootstrapping, EHCM and addition operations of multiple matrices, can be accelerated by parallel. This parallel may accelerate the bootstrapping. At last, we found a set of more efficient combination of parameters. As a result, our security parameter level is 128 bits and the correctness is elevated, compared with TFHE scheme in ASIACRYPT 2016. Experiments show that the running time of our bootstrapping is 10ms, which is only 52 percent of TFHE, and is less than CGGI17.

Note: We have updated the experimental data and rewritten portions of text.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
fully homomorphic encryptionbootstrapping processaccumulatorTFHE
Contact author(s)
850301775 @ qq com
2017-11-05: revised
2017-08-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {TanPing ZHOU and XiaoYuan YANG and LongFei LIU and Wei ZHANG and YiTao DING},
      title = {Faster Bootstrapping with Multiple Addends},
      howpublished = {Cryptology ePrint Archive, Paper 2017/735},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.