Cryptology ePrint Archive: Report 2021/729

Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE

Ilaria Chillotti and Damien Ligier and Jean-Baptiste Orfila and Samuel Tap

Abstract: Fully Homomorphic Encryption (FHE) schemes enable to compute over encrypted data. Among them, TFHE [CGGI17] has the great advantage of offering an efficient method for bootstrapping noisy ciphertexts, i.e., reduce the noise. Indeed, homomorphic computation increases the noise in ciphertexts and might compromise the encrypted message. TFHE bootstrapping, in addition to reducing the noise, also evaluates (for free) univariate functions expressed as look-up tables. It however requires to have the most significant bit of the plaintext to be known a priori, resulting in the loss of one bit of space to store messages. Furthermore it represents a non negligible overhead in terms of computation in many use cases.

In this paper, we propose a solution to overcome this limitation, that we call Programmable Bootstrapping Without Padding (WoP-PBS). This approach relies on two building blocks. The first one is the multiplication à la BFV [FV12] that we incorporate into TFHE. This is possible thanks to a thorough noise analysis showing that correct multiplications can be computed using practical TFHE parameters. The second building block is the generalization of TFHE bootstrapping introduced in this paper. It offers the flexibility to select any chunk of bits in an encrypted plaintext during a bootstrap. It also enables to evaluate many LUTs at the same time when working with small enough precision. All these improvements are particularly helpful in some applications such as the evaluation of Boolean circuits (where a bootstrap is no longer required in each evaluated gate) and, more generally, in the efficient evaluation of arithmetic circuits even with large integers. Those results improve TFHE circuit bootstrapping as well. Moreover, we show that bootstrapping large precision integers is now possible using much smaller parameters than those obtained by scaling TFHE ones.

Category / Keywords: FHE, TFHE, Bootstrapping, Multiplication

Original Publication (with major differences): IACR-ASIACRYPT-2021

Date: received 31 May 2021, last revised 24 Nov 2021

Contact author: ilaria chillotti at zama ai, damien ligier at zama ai, jb orfila at zama ai, samuel tap at zama ai

Available format(s): PDF | BibTeX Citation

Version: 20211124:205936 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]