On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis
CASTAGNOS, Guilhem
Institut de Mathématiques de Bordeaux [IMB]
Equipe AMACC - Laboratoire GREYC - UMR6072
Institut de Mathématiques de Bordeaux [IMB]
Equipe AMACC - Laboratoire GREYC - UMR6072
CASTAGNOS, Guilhem
Institut de Mathématiques de Bordeaux [IMB]
Equipe AMACC - Laboratoire GREYC - UMR6072
< Réduire
Institut de Mathématiques de Bordeaux [IMB]
Equipe AMACC - Laboratoire GREYC - UMR6072
Langue
en
Communication dans un congrès
Ce document a été publié dans
Lecture Notes in Computer Science, Lecture Notes in Computer Science, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2009-12-06, Tokyo. 2009p. 260 - 277
Résumé en anglais
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 ...Lire la suite >
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.< Réduire
Mots clés en anglais
Polynomial time total break
quadratic decryption
NICE cryptosystems
imaginary quadratic field-based cryptography
Origine
Importé de halUnités de recherche