Bootstrapping in FHEW-like Cryptosystems

Daniele Micciancio, Yuriy Polyakov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationWAHC 2021 - Proceedings of the 9th Workshop on Encrypted Computing and Applied Homomorphic Cryptography, co-located with CCS 2021
PublisherAssociation for Computing Machinery, Inc
Pages17-28
Number of pages12
ISBN (Electronic)9781450386562
DOIs
StatePublished - Nov 15 2021
Externally publishedYes
Event9th Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2021, co-located with CCS 2021 - Virtual, Online, Korea, Republic of
Duration: Nov 15 2021 → …

Publication series

NameWAHC 2021 - Proceedings of the 9th Workshop on Encrypted Computing and Applied Homomorphic Cryptography, co-located with CCS 2021

Conference

Conference9th Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2021, co-located with CCS 2021
Country/TerritoryKorea, Republic of
CityVirtual, Online
Period11/15/21 → …

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications

Keywords

  • bootstrapping
  • fhew
  • fully homomorphic encryption
  • software implementation
  • tfhe

Fingerprint

Dive into the research topics of 'Bootstrapping in FHEW-like Cryptosystems'. Together they form a unique fingerprint.

Cite this