CASTAGNOS, Guilhem; JOUX, Antoine; LAGUILLAUMIE, Fabien; NGUYEN, Phong Q.

doi:10.1007/978-3-642-10366-7_28

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

CASTAGNOS, Guilhem
Institut de Mathématiques de Bordeaux [IMB]

JOUX, Antoine
Parallélisme, Réseaux, Systèmes, Modélisation [PRISM]
Délégation générale de l'armement [DGA]

LAGUILLAUMIE, Fabien
Equipe AMACC - Laboratoire GREYC - UMR6072

Langue

Communication dans un congrès

Ce document a été publié dans

Lecture Notes in Computer Science, Lecture Notes in Computer Science, 15th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2009, 2009-12-06, Tokyo. 2009p. 469 - 486

Résumé en anglais

We present a new algorithm based on binary quadratic forms to factor integers of the form N = pq 2 . Its heuristic running time is expo-nential in the general case, but becomes polynomial when special (arith-metic) hints are available, which is exactly the case for the so-called NICE family of public-key cryptosystems based on quadratic fields introduced in the late 90s. Such cryptosystems come in two flavours, depending on whether the quadratic field is imaginary or real. Our factoring al-gorithm yields a general key-recovery polynomial-time attack on NICE, which works for both versions: Castagnos and Laguillaumie recently ob-tained a total break of imaginary-NICE, but their attack could not apply to real-NICE. Our algorithm is rather different from classical factoring algorithms: it combines Lagrange's reduction of quadratic forms with a provable variant of Coppersmith's lattice-based root finding algorithm for homogeneous polynomials. It is very efficient given either of the following arithmetic hints: the public key of imaginary-NICE, which provides an alternative to the CL attack; or the knowledge that the regulator of the quadratic field Q(√ p) is unusually small, just like in real-NICE.< Réduire

Mots clés en anglais

Public-key Cryptanalysis

Factorisation

Binary Quadratic Forms

Homogeneous Coppersmith's Root Finding

Lattices

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Factoring pq 2 with Quadratic Forms: Nice Cryptanalyses

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

DOI

Origine

Unités de recherche