### Fully Homomorphic Encryption with Polylog Overhead

Craig Gentry, Shai Halevi, and 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. extended abstract in Eurocrypt 2012
Keywords
Homomorphic encryptionBootstrappingBatchingAutomorphismGalois groupPermutation network
Contact author(s)
shaih @ alum mit edu
History
2012-04-05: last of 2 revisions
See all versions
Short URL
https://ia.cr/2011/566

CC BY

BibTeX

@misc{cryptoeprint:2011/566,
author = {Craig Gentry and Shai Halevi and Nigel P.  Smart},
title = {Fully Homomorphic Encryption with Polylog Overhead},
howpublished = {Cryptology ePrint Archive, Paper 2011/566},
year = {2011},
note = {\url{https://eprint.iacr.org/2011/566}},
url = {https://eprint.iacr.org/2011/566}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.