2014 | OriginalPaper | Buchkapitel
Faster Bootstrapping with Polynomial Error
verfasst von : Jacob Alperin-Sheriff, Chris Peikert
Erschienen in: Advances in Cryptology – CRYPTO 2014
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Bootstrapping
is a technique, originally due to Gentry (STOC 2009), for “refreshing” ciphertexts of a somewhat homomorphic encryption scheme so that they can support further homomorphic operations. To date, bootstrapping remains the only known way of obtaining fully homomorphic encryption for arbitrary unbounded computations.
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
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
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
small
polynomials. Unlike most previous methods, ours implements an elementary and efficient
arithmetic
procedure, thereby avoiding the inefficiencies inherent to the use of boolean circuits and Barrington’s Theorem. For 2
λ
security under conventional lattice assumptions, our method requires only a
quasi-linear
Õ(
λ
) 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.