Factoring pq 2 with Quadratic Forms: Nice Cryptanalyses

Guilhem Castagnos (1) , Antoine Joux (2, 3) , Fabien Laguillaumie (4) , Phong Q. Nguyen (5, 6)

1 IMB - Institut de Mathématiques de Bordeaux
2 PRISM - Parallélisme, Réseaux, Systèmes, Modélisation
3 DGA - Délégation générale de l'armement
4 Equipe AMACC - Laboratoire GREYC - UMR6072
5 LIENS - Laboratoire d'informatique de l'école normale supérieure
6 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities

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.

Mots clés: Public-key Cryptanalysis; Factorisation; Binary Quadratic Forms; Homogeneous Coppersmith's Root Finding; Lattices

Domaines: Algorithme et structure de données [cs.DS]; Informatique [cs]; Cryptographie et sécurité [cs.CR]

Guilhem Castagnos, Antoine Joux, Fabien Laguillaumie, Phong Q. Nguyen. Factoring pq 2 with Quadratic Forms: Nice Cryptanalyses. 15th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2009, Dec 2009, Tokyo, Japan. pp.469 - 486, ⟨10.1007/978-3-642-10366-7_28⟩. ⟨hal-01082340⟩