Fully Homomorphic Encryption over the Integers with Shorter Public Keys

Jean-Sébastien Coron 1 Avradip Mandal 1 David Naccache 2, 3 Mehdi Tibouchi 2, 3
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : At Eurocrypt 2010 van Dijk et al. described a fully homomorphic encryption scheme over the integers. The main appeal of this scheme (compared to Gentry’s) is its conceptual simplicity. This simplicity comes at the expense of a public key size in O~(λ10) which is too large for any practical system. In this paper we reduce the public key size to O~(λ7) by encrypting with a quadratic form in the public key elements, instead of a linear form. We prove that the scheme remains semantically secure, based on a stronger variant of the approximate-GCD problem, already considered by van Dijk et al. We also describe the first implementation of the resulting fully homomorphic scheme. Borrowing some optimizations from the recent Gentry-Halevi implementation of Gentry’s scheme, we obtain roughly the same level of efficiency. This shows that fully homomorphic encryption can be implemented using simple arithmetic operations.
Type de document :
Communication dans un congrès
Phillip Rogaway. CRYPTO 2011 - 31st Annual Cryptology Conference, Aug 2011, Santa Barbara, CA, United States. Springer, 6841, pp.487-504, 2011, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-642-22792-9_28〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01110216
Contributeur : Brigitte Briot <>
Soumis le : mardi 27 janvier 2015 - 16:44:09
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

Collections

Citation

Jean-Sébastien Coron, Avradip Mandal, David Naccache, Mehdi Tibouchi. Fully Homomorphic Encryption over the Integers with Shorter Public Keys. Phillip Rogaway. CRYPTO 2011 - 31st Annual Cryptology Conference, Aug 2011, Santa Barbara, CA, United States. Springer, 6841, pp.487-504, 2011, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-642-22792-9_28〉. 〈hal-01110216〉

Partager

Métriques

Consultations de la notice

153