On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis

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.