Paper 2018/532

Ring packing and amortized FHEW bootstrapping

Daniele Micciancio and Jessica Sorrell

Abstract

The FHEW fully homomorphic encryption scheme (Ducas and Micciancio, Eurocrypt 2015) offers very fast homomorphic NAND-gate computations (on encrypted data) and a relatively fast refreshing procedure that allows to homomorphically evaluate arbitrary NAND boolean circuits. Unfortunately, the refreshing procedure needs to be executed after every single NAND computation, and each refreshing operates on a single encrypted bit, greatly decreasing the overall throughput of the scheme. We give a new refreshing procedure that simultaneously refreshes $n$ FHEW ciphertexts, at a cost comparable to a single-bit FHEW refreshing operation. As a result, the cost of each refreshing is amortized over $n$ encrypted bits, improving the throughput for the homomorphic evaluation of boolean circuits roughly by a factor $n$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. ICALP 2018
DOI
10.4230/LIPIcs.ICALP.2018.100
Keywords
Fully Homomorphic EncryptionBootstrappingLattice-based Cryptography
Contact author(s)
jlsorrel @ eng ucsd edu
History
2019-10-06: revised
2018-06-04: received
See all versions
Short URL
https://ia.cr/2018/532
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/532,
      author = {Daniele Micciancio and Jessica Sorrell},
      title = {Ring packing and amortized FHEW bootstrapping},
      howpublished = {Cryptology ePrint Archive, Paper 2018/532},
      year = {2018},
      doi = {10.4230/LIPIcs.ICALP.2018.100},
      note = {\url{https://eprint.iacr.org/2018/532}},
      url = {https://eprint.iacr.org/2018/532}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.