Afficher la notice abrégée

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.identifierConstruction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities [CASCADE]
dc.contributor.authorNGUYEN, Phong Q.
dc.contributor.editorSpringer Berlin Heidelberg
dc.date.accessioned2024-04-04T03:21:58Z
dc.date.available2024-04-04T03:21:58Z
dc.date.issued2009
dc.date.conference2009-12-06
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/194708
dc.description.abstractEnWe present a new algorithm based on binary quadratic forms to factor integers of the form N = pq². Its heuristic running time is exponential in the general case, but becomes polynomial when special (arithmetic) 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 algorithm yields a general key-recovery polynomial-time attack on NICE, which works for both versions: Castagnos and Laguillaumie recently obtained 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.subject.enLattices
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² with Quadratic Forms: Nice Cryptanalyses
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-10366-7
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.issue5912
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleASIACRYPT'2009 - 15th Annual International Conference on the Theory and Application of Cryptology and Information Security, A
bordeaux.countryJP
bordeaux.conference.cityTokyo
bordeaux.peerReviewedoui
hal.identifierhal-01022756
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2009-12-10
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01022756v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2009&rft.issue=5912&rft.spage=469-486&rft.epage=469-486&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