FHEW: Bootstrapping Homomorphic Encryption in less than a second

Léo Ducas; Daniele Micciancio

Paper 2014/816

FHEW: Bootstrapping Homomorphic Encryption in less than a second

Léo Ducas and Daniele Micciancio

Abstract

The main bottleneck affecting the efficiency of all known fully homomorphic encryption (FHE) schemes is Gentry’s bootstrapping procedure, which is required to refresh noisy ciphertexts and keep computing on encrypted data. Bootstrapping in the latest implementation of FHE, the HElib library of Halevi and Shoup (Crypto 2014), requires about six minutes per batch. We present a new method to homomorphically compute simple bit operations, and refresh (bootstrap) the resulting output, which runs on a personal computer in just about half a second. We present a detailed technical analysis of the scheme (based on the worst-case hardness of standard lattice problems) and report on the performance of our prototype implementation.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: FHE bootstrapping Ring-LWE
Contact author(s): lducas @ eng ucsd edu
History: 2015-03-02: last of 3 revisions; 2014-10-11: received; See all versions
Short URL: https://ia.cr/2014/816
License: CC BY

BibTeX

@misc{cryptoeprint:2014/816,
      author = {Léo Ducas and Daniele Micciancio},
      title = {{FHEW}: Bootstrapping Homomorphic Encryption in less than a second},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/816},
      year = {2014},
      url = {https://eprint.iacr.org/2014/816}
}