Factoring pq 2 with Quadratic Forms: Nice Cryptanalyses
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | CASTAGNOS, Guilhem | |
| hal.structure.identifier | Parallélisme, Réseaux, Systèmes, Modélisation [PRISM] | |
| hal.structure.identifier | Délégation générale de l'armement [DGA] | |
| dc.contributor.author | JOUX, Antoine | |
| hal.structure.identifier | Equipe AMACC - Laboratoire GREYC - UMR6072 | |
| dc.contributor.author | LAGUILLAUMIE, Fabien | |
| hal.structure.identifier | Laboratoire d'informatique de l'école normale supérieure [LIENS] | |
| hal.structure.identifier | Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities [CASCADE] | |
| dc.contributor.author | NGUYEN, Phong Q. | |
| dc.date.accessioned | 2024-04-04T03:20:11Z | |
| dc.date.available | 2024-04-04T03:20:11Z | |
| dc.date.issued | 2009 | |
| dc.date.conference | 2009-12-06 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/194570 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.source.title | Lecture Notes in Computer Science | |
| dc.subject.en | Public-key Cryptanalysis | |
| dc.subject.en | Factorisation | |
| dc.subject.en | Binary Quadratic Forms | |
| dc.subject.en | Homogeneous Coppersmith's Root Finding | |
| dc.subject.en | Lattices | |
| dc.title.en | Factoring pq 2 with Quadratic Forms: Nice Cryptanalyses | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1007/978-3-642-10366-7_28 | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| dc.subject.hal | Informatique [cs] | |
| dc.subject.hal | Informatique [cs]/Cryptographie et sécurité [cs.CR] | |
| bordeaux.page | 469 - 486 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | 15th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2009 | |
| bordeaux.country | JP | |
| bordeaux.title.proceeding | Lecture Notes in Computer Science | |
| bordeaux.conference.city | Tokyo | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01082340 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2009-12-10 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01082340v1 | |
| bordeaux.COinS | ctx_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 |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||