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
FHEbootstrappingRing-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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2014/816}},
      url = {https://eprint.iacr.org/2014/816}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.