15665

Amortized FHEW Bootstrapping

APA

(2020). Amortized FHEW Bootstrapping. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/amortized-fhew-bootstrapping

MLA

Amortized FHEW Bootstrapping. The Simons Institute for the Theory of Computing, May. 01, 2020, https://simons.berkeley.edu/talks/amortized-fhew-bootstrapping

BibTex

          @misc{ scivideos_15665,
            doi = {},
            url = {https://simons.berkeley.edu/talks/amortized-fhew-bootstrapping},
            author = {},
            keywords = {},
            language = {en},
            title = {Amortized FHEW Bootstrapping},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {may},
            note = {15665 see, \url{https://scivideos.org/Simons-Institute/15665}}
          }
          
Jessica Sorrell, UC San Diego
Talk number15665
Source RepositorySimons Institute

Abstract

The FHEW fully homomorphic encryption scheme of Ducas and Micciancio 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.