Cryptology ePrint Archive: Report 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$.

Category / Keywords: public-key cryptography / Fully Homomorphic Encryption, Bootstrapping, Lattice-based Cryptography

Original Publication (with major differences): ICALP 2018

Date: received 30 May 2018, last revised 6 Oct 2019

Contact author: jlsorrel at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20191006:201700 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]