Paper 2021/729
Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE
Ilaria Chillotti, Damien Ligier, 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.
Metadata
- Available format(s)
-
PDF
- Publication info
- A major revision of an IACR publication in ASIACRYPT 2021
- Keywords
- FHETFHEBootstrappingMultiplication
- Contact author(s)
-
ilaria chillotti @ zama ai
damien ligier @ zama ai
jb orfila @ zama ai
samuel tap @ zama ai - History
- 2021-11-24: last of 2 revisions
- 2021-06-02: received
- See all versions
- Short URL
- https://ia.cr/2021/729
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/729,
author = {Ilaria Chillotti and Damien Ligier and Jean-Baptiste Orfila and Samuel Tap},
title = {Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for {TFHE}},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/729},
year = {2021},
url = {https://eprint.iacr.org/2021/729}
}