Factoring pq² 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 | Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities [CASCADE] | |
| dc.contributor.author | NGUYEN, Phong Q. | |
| dc.contributor.editor | Springer Berlin Heidelberg | |
| dc.date.accessioned | 2024-04-04T03:21:58Z | |
| dc.date.available | 2024-04-04T03:21:58Z | |
| dc.date.issued | 2009 | |
| dc.date.conference | 2009-12-06 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/194708 | |
| dc.description.abstractEn | We 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.iso | en | |
| dc.subject.en | Lattices | |
| 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² with Quadratic Forms: Nice Cryptanalyses | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1007/978-3-642-10366-7 | |
| 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.issue | 5912 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | ASIACRYPT'2009 - 15th Annual International Conference on the Theory and Application of Cryptology and Information Security, A | |
| bordeaux.country | JP | |
| bordeaux.conference.city | Tokyo | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01022756 | |
| 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-01022756v1 | |
| bordeaux.COinS | ctx_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 |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||