2009 | OriginalPaper | Chapter
On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis
Authors : Guilhem Castagnos, Fabien Laguillaumie
Published in: Advances in Cryptology - EUROCRYPT 2009
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We describe the first
polynomial time chosen-plaintext total break
of the
NICE
family of cryptosystems based on ideal arithmetic in imaginary quadratic orders, introduced in the late 90’s by Hartmann, Paulus and Takagi [HPT99]. The singular interest of these encryption 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
$\Delta_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.