Scale-Invariant Fully-Homomorphic Encryption over the Integers

Abstract : At Crypto 2012, Brakerski constructed a scale-invariant fully homomorphic encryption scheme based on the LWE problem, in which the same modulus is used throughout the evaluation process, instead of a ladder of moduli when doing "modulus switching". In this paper we describe a variant of the van Dijk et al. FHE scheme over the integers with the same scale-invariant property. Our scheme has a single secret modulus whose size is linear in the multiplicative depth of the circuit to be homomorphically evaluated, instead of exponential; we therefore construct a leveled fully homomorphic encryption scheme. This scheme can be transformed into a pure fully homomorphic encryption scheme using bootstrapping, and its security is still based on the Approximate-GCD problem. We also describe an implementation of the homomorphic evaluation of the full AES encryption circuit, and obtain significantly improved performance compared to previous implementations: about 23 seconds (resp. 3 minutes) per AES block at the 72-bit (resp. 80-bit) security level on a mid-range workstation. Finally, we prove the equivalence between the (error-free) decisional Approximate-GCD problem introduced by Cheon et al. (Eurocrypt 2013) and the classical computational Approximate-GCD problem. This equivalence allows to get rid of the additional noise in all the integer-based FHE schemes described so far, and therefore to simplify their security proof.
Type de document :
Communication dans un congrès
Hugo Krawczyk. PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Mar 2014, Buenos Aires, Argentina. Springer, 8383, pp.311-328, 2014, Public-Key Cryptography - PKC 2014. 〈10.1007/978-3-642-54631-0_18〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00950481
Contributeur : Tancrède Lepoint <>
Soumis le : vendredi 21 février 2014 - 14:49:57
Dernière modification le : mardi 24 avril 2018 - 17:20:13

Lien texte intégral

Identifiants

Collections

Citation

Tancrède Lepoint, Jean-Sébastien Coron, Mehdi Tibouchi. Scale-Invariant Fully-Homomorphic Encryption over the Integers. Hugo Krawczyk. PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Mar 2014, Buenos Aires, Argentina. Springer, 8383, pp.311-328, 2014, Public-Key Cryptography - PKC 2014. 〈10.1007/978-3-642-54631-0_18〉. 〈hal-00950481〉

Partager

Métriques

Consultations de la notice

425