### Bootstrapping in FHEW-like Cryptosystems

##### Abstract

FHEW and TFHE are fully homomorphic encryption (FHE) cryptosystems that can evaluate arbitrary Boolean circuits on encrypted data by bootstrapping after each gate evaluation. The FHEW cryptosystem was originally designed based on standard (Ring, circular secure) LWE assumptions, and its initial implementation was able to run bootstrapping in less than 1 second. The TFHE cryptosystem used somewhat stronger assumptions, such as (Ring, circular secure) LWE over the torus with binary secret distribution, and applied several other optimizations to reduce the bootstrapping runtime to less than 0.1 second. Up to now, the gap between the underlying security assumptions prevented a fair comparison of the cryptosystems for the same security settings. We present a unified framework that includes the original and extended variants of both FHEW and TFHE cryptosystems, and implement it in the open-source PALISADE lattice cryptography library using modular arithmetic. Our analysis shows that the main distinction between the cryptosystems is the bootstrapping procedure used: Alperin-Sherif--Peikert (AP) for FHEW vs. Gama--Izabachene--Nguyen--Xie (GINX) for TFHE. All other algorithmic optimizations in TFHE equally apply to both cryptosystems. The GINX bootstrapping method makes essential the use of binary secrets, and cannot be directly applied to other secret distributions. In the process of comparing the two schemes, we present a simple, lightweight method to extend GINX bootstrapping (e.g., as employed by TFHE) to ternary uniform and Gaussian secret distributions, which are included in the HE community security standard. Our comparison of the AP and GINX bootstrapping methods for different secret distributions suggests that the TFHE/GINX cryptosystem provides better performance for binary and ternary secrets while FHEW/AP is faster for Gaussian secrets. We make a recommendation to consider the variants of FHEW and TFHE cryptosystems based on ternary and Gaussian secrets for standardization by the HE community.

Note: Minor revisions: updated the bootstrapping key size estimate.

Available format(s)
Category
Implementation
Publication info
Published elsewhere. WAHC 2021 – 9th Workshop on Encrypted Computing & Applied Homomorphic Cryptography
Keywords
implementation fully homomorphic encryption lattice techniques programmable bootstrapping FHEW DM TFHE CGGI
Contact author(s)
ypolyakov @ dualitytech com
History
2022-10-23: last of 9 revisions
See all versions
Short URL
https://ia.cr/2020/086

CC BY

BibTeX

@misc{cryptoeprint:2020/086,
author = {Daniele Micciancio and Yuriy Polyakov},
title = {Bootstrapping in FHEW-like Cryptosystems},
howpublished = {Cryptology ePrint Archive, Paper 2020/086},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/086}},
url = {https://eprint.iacr.org/2020/086}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.