Welcome to the resource topic for 2011/566
Title:
Fully Homomorphic Encryption with Polylog Overhead
Authors: Craig Gentry, Shai Halevi, Nigel P. Smart
Abstract:We show that homomorphic evaluation of (wide enough) arithmetic circuits can be accomplished with only polylogarithmic overhead. Namely, we present a construction of fully homomorphic encryption (FHE) schemes that for security parameter \secparam can evaluate any width-\Omega(\secparam) circuit with t gates in time t\cdot polylog(\secparam). To get low overhead, we use the recent batch homomorphic evaluation techniques of Smart-Vercauteren and Brakerski-Gentry-Vaikuntanathan, who showed that homomorphic operations can be applied to “packed” ciphertexts that encrypt vectors of plaintext elements. In this work, we introduce permuting/routing techniques to move plaintext elements across these vectors efficiently. Hence, we are able to implement general arithmetic circuit in a batched fashion without ever needing to “unpack” the plaintext vectors. We also introduce some other optimizations that can speed up homomorphic evaluation in certain cases. For example, we show how to use the Frobenius map to raise plaintext elements to powers of~p at the “cost” of a linear operation.
ePrint: https://eprint.iacr.org/2011/566
Talk: https://www.youtube.com/watch?v=dIUU24jBFok
Slides: https://iacr.org/cryptodb/archive/2012/EUROCRYPT/presentation/24272.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .