Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
verfasst von : Craig Gentry
Erschienen in: Advances in Cryptology – CRYPTO 2010
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
Gentry proposed a fully homomorphic public key encryption scheme that uses ideal lattices. He based the security of his scheme on the hardness of two problems: an average-case decision problem over ideal lattices, and the sparse (or “low-weight”) subset sum problem (SSSP).
We provide a key generation algorithm for Gentry’s scheme that generates ideal lattices according to a “nice” average-case distribution. Then, we prove a worst-case / average-case connection that bases Gentry’s scheme (in part) on the quantum hardness of the shortest independent vector problem (SIVP) over ideal lattices in the
worst-case
. (We cannot remove the need to assume that the SSSP is hard.) Our worst-case / average-case connection is the first where the average-case lattice is an ideal lattice, which seems to be necessary to support the security of Gentry’s scheme.