On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis
hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
hal.structure.identifier | Equipe AMACC - Laboratoire GREYC - UMR6072 | |
dc.contributor.author | CASTAGNOS, Guilhem | |
hal.structure.identifier | Equipe AMACC - Laboratoire GREYC - UMR6072 | |
dc.contributor.author | LAGUILLAUMIE, Fabien | |
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/194569 | |
dc.description.abstractEn | We describe the first polynomial time chosen-plaintext to-tal break of the NICE family of cryptosystems based on ideal arith-metic in imaginary quadratic orders, introduced in the late 90's by Hart-mann, Paulus and Takagi [HPT99]. The singular interest of these en-cryption schemes is their natural quadratic decryption time procedure that consists essentially in applying Euclid's algorithm. The only current specific cryptanalysis of these schemes is Jaulmes and Joux's chosen-ciphertext attack to recover the secret key [JJ00]. Originally, Hartmann et al. claimed that the security against a total break attack relies only on the difficulty of factoring the public discriminant ∆q = −pq 2 , although the public key was also composed of a specific element of the class group of the order of discriminant ∆q, which is crucial to reach the quadratic decryption complexity. In this article, we propose a drastic cryptanalysis which factors ∆q (and hence recovers the secret key), only given this element, in cubic time in the security parameter. As a result, performing our cryptanalysis on a cryptographic example takes less than a second on a standard PC. | |
dc.language.iso | en | |
dc.source.title | Lecture Notes in Computer Science | |
dc.subject.en | Polynomial time total break | |
dc.subject.en | quadratic decryption | |
dc.subject.en | NICE cryptosystems | |
dc.subject.en | imaginary quadratic field-based cryptography | |
dc.title.en | On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis | |
dc.type | Communication dans un congrès | |
dc.identifier.doi | 10.1007/978-3-642-01001-9_15 | |
dc.subject.hal | Informatique [cs] | |
dc.subject.hal | Informatique [cs]/Cryptographie et sécurité [cs.CR] | |
bordeaux.page | 260 - 277 | |
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 | 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques | |
bordeaux.country | JP | |
bordeaux.title.proceeding | Lecture Notes in Computer Science | |
bordeaux.conference.city | Tokyo | |
bordeaux.peerReviewed | oui | |
hal.identifier | hal-01082343 | |
hal.version | 1 | |
hal.invited | non | |
hal.proceedings | oui | |
hal.conference.end | 2012-12-10 | |
hal.popular | non | |
hal.audience | Internationale | |
hal.origin.link | https://hal.archives-ouvertes.fr//hal-01082343v1 | |
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=260%20-%20277&rft.epage=260%20-%20277&rft.au=CASTAGNOS,%20Guilhem&LAGUILLAUMIE,%20Fabien&rft.genre=unknown |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |