Afficher la notice abrégée

Factoring pq 2 with Quadratic Forms: Nice Cryptanalyses

hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorCASTAGNOS, Guilhem
hal.structure.identifierParallélisme, Réseaux, Systèmes, Modélisation [PRISM]
hal.structure.identifierDélégation générale de l'armement [DGA]
dc.contributor.authorJOUX, Antoine
hal.structure.identifierEquipe AMACC - Laboratoire GREYC - UMR6072
dc.contributor.authorLAGUILLAUMIE, Fabien
hal.structure.identifierLaboratoire d'informatique de l'école normale supérieure [LIENS]
hal.structure.identifierConstruction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities [CASCADE]
dc.contributor.authorNGUYEN, Phong Q.
dc.date.accessioned2024-04-04T03:20:11Z
dc.date.available2024-04-04T03:20:11Z
dc.date.issued2009
dc.date.conference2009-12-06
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/194570
dc.description.abstractEnWe 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.
dc.language.isoen
dc.source.titleLecture Notes in Computer Science
dc.subject.enPublic-key Cryptanalysis
dc.subject.enFactorisation
dc.subject.enBinary Quadratic Forms
dc.subject.enHomogeneous Coppersmith's Root Finding
dc.subject.enLattices
dc.title.enFactoring pq 2 with Quadratic Forms: Nice Cryptanalyses
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-10366-7_28
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]
dc.subject.halInformatique [cs]/Cryptographie et sécurité [cs.CR]
bordeaux.page469 - 486
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.title15th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2009
bordeaux.countryJP
bordeaux.title.proceedingLecture Notes in Computer Science
bordeaux.conference.cityTokyo
bordeaux.peerReviewedoui
hal.identifierhal-01082340
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2009-12-10
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01082340v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Lecture%20Notes%20in%20Computer%20Science&rft.date=2009&rft.spage=469%20-%20486&rft.epage=469%20-%20486&rft.au=CASTAGNOS,%20Guilhem&JOUX,%20Antoine&LAGUILLAUMIE,%20Fabien&NGUYEN,%20Phong%20Q.&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée