Abstract
We present a chosen-ciphertext attack against both NICE cryptosystems. These two cryptosystems are based on computations in the class group of non-maximal imaginary orders. More precisely, the systems make use of the canonical surjection between the class group of the quadratic order of discriminant \( \sqrt { - pq^2 } \) and the class group of the quadratic order of discriminant \( \sqrt { - p} \). In this paper, we examine the properties of this canonical surjection and use them to build a chosen-ciphertext attack that recovers the secret key (p and q) from two ciphertexts/cleartexts pairs.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryption — how to encrypt with RSA. In A. De Santis, editor, Advances in Cryptology — EUROCRYPT’94, volume 950 of Lecture Notes in Computer Science. Springer-Verlag, 1994.
Dan Boneh, Glenn Durfee, and Nick Howgrave-Graham. Factoring n = pq r for large r. In M. Wiener, editor, Advances in Cryptology — CRYPTO’99, volume 1666 of Lecture Notes in Computer Science, pages 326–337. Springer, 1999.
Henri Cohen. A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics. Springer, 1995.
T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31:469–472, 1985.
M. Hartmann, S. Paulus, and T. Takagi. Nice-new ideal coset encryption. In Çetin K. Koç and Christof Paar, editors, Cryptographic Hardware and Embedded Systems — CHES’99, pages 341–352. Springer Verlag, 1999. Pre-proceedings, final proceedings to appear in LNCS.
Hühnlein and Takagi. Reducing logarithms in totally non-maximal orders to logarithms in finite fields. In ASIACRYPT’99, 1999.
D. Hühnlein, M. J. Jacobson, S. Paulus Jr., and T. Takagi. A cryptosystem based on non-maximal imaginary quadratic orders with fast decryption. In Avances in Cryptology — EUROCRYPT’98, volume 1403 of Lecture Notes in Computer Science, pages 294–307, 1998.
Sachar Paulus and Tsuyoshi Takagi. A new public-key cryptosystem over quadratic orders with quadratic decryption time. to appear in Journal of Cryptology.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jaulmes, É., Joux, A. (2000). A NICE Cryptanalysis. In: Preneel, B. (eds) Advances in Cryptology — EUROCRYPT 2000. EUROCRYPT 2000. Lecture Notes in Computer Science, vol 1807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45539-6_26
Download citation
DOI: https://doi.org/10.1007/3-540-45539-6_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67517-4
Online ISBN: 978-3-540-45539-4
eBook Packages: Springer Book Archive