Cryptology ePrint Archive: Report 2017/735

Faster Bootstrapping with Multiple Addends

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

Abstract: 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.

Category / Keywords: public-key cryptography / fully homomorphic encryption, bootstrapping process, accumulator, TFHE

Date: received 30 Jul 2017, last revised 4 Nov 2017

Contact author: 850301775 at qq com

Available format(s): PDF | BibTeX Citation

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

Version: 20171105:034640 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]