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
< Leer menos
Institut de Mathématiques de Bordeaux [IMB]
Equipe AMACC - Laboratoire GREYC - UMR6072
Idioma
en
Communication dans un congrès
Este ítem está publicado en
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
Resumen en inglés
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 ...Leer más >
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.< Leer menos
Palabras clave en inglés
Polynomial time total break
quadratic decryption
NICE cryptosystems
imaginary quadratic field-based cryptography
Orígen
Importado de HalCentros de investigación