Over the past few years, several works have dramatically improved the efficiency of bootstrapping and the hardness assumptions needed to implement it. Recently, Brakerski and Vaikuntanathan~(ITCS~2014) reached the major milestone of a bootstrapping algorithm based on Learning With Errors for \emph{polynomial} approximation factors. Their method uses the Gentry-Sahai-Waters~(GSW) cryptosystem~(CRYPTO~2013) in conjunction with Barrington's ``circuit sequentialization'' theorem~(STOC~1986). This approach, however, results in \emph{very large} polynomial runtimes and approximation factors. (The approximation factors can be improved, but at even greater costs in runtime and space.)
In this work we give a new bootstrapping algorithm whose runtime and associated approximation factor are both \emph{small} polynomials. Unlike most previous methods, ours implements an elementary and efficient \emph{arithmetic} procedure, thereby avoiding the inefficiencies inherent to the use of boolean circuits and Barrington's Theorem. For $2^{\lambda}$ security under conventional lattice assumptions, our method requires only a \emph{quasi-linear} $\Otil(\lambda)$ number of homomorphic operations on GSW ciphertexts, which is optimal (up to polylogarithmic factors) for schemes that encrypt just one bit per ciphertext. As a contribution of independent interest, we also give a technically simpler variant of the GSW system and a tighter error analysis for its homomorphic operations.
Category / Keywords: bootstrapping, fully homomorphic encryption Original Publication (with major differences): IACR-CRYPTO-2014 Date: received 9 Feb 2014, last revised 13 Jun 2014 Contact author: cpeikert at cc gatech edu Available format(s): PDF | BibTeX Citation Version: 20140614:002953 (All versions of this report) Short URL: ia.cr/2014/094 Discussion forum: Show discussion | Start new discussion