Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers

Yuanmi Chen 1 Phong Q. Nguyen 2, 3
3 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : At EUROCRYPT '10, van Dijk et al. presented simple fully- homomorphic encryption (FHE) schemes based on the hardness of approximate integer common divisors problems, which were introduced in 2001 by Howgrave-Graham. There are two versions for these problems: the partial version (PACD) and the general version (GACD). The seemingly easier problem PACD was recently used by Coron et al. at CRYPTO '11 to build a more efficient variant of the FHE scheme by van Dijk et al.. We present a new PACD algorithm whose running time is essentially the "square root" of that of exhaustive search, which was the best attack in practice. This allows us to experimentally break the FHE challenges proposed by Coron et al. Our PACD algorithm directly gives rise to a new GACD algorithm, which is exponentially faster than exhaustive search. Interestingly, our main technique can also be applied to other settings, such as noisy factoring and attacking low-exponent RSA.
Type de document :
Communication dans un congrès
David Pointcheval and Thomas Johansson. EUROCRYPT 2012, Apr 2012, Cambridge, United Kingdom. Springer, 7237, pp.502-519, 2012, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007%2F978-3-642-29011-4_30〉. 〈10.1007/978-3-642-29011-4_30〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00864374
Contributeur : Phong Q. Nguyen <>
Soumis le : samedi 21 septembre 2013 - 09:09:27
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : vendredi 7 avril 2017 - 00:52:26

Fichier

ChenNguyen.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Yuanmi Chen, Phong Q. Nguyen. Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers. David Pointcheval and Thomas Johansson. EUROCRYPT 2012, Apr 2012, Cambridge, United Kingdom. Springer, 7237, pp.502-519, 2012, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007%2F978-3-642-29011-4_30〉. 〈10.1007/978-3-642-29011-4_30〉. 〈hal-00864374〉

Partager

Métriques

Consultations de la notice

460

Téléchargements de fichiers

614