Abstract
In a series of papers Patarin proposes new efficient public key systems. A very interesting proposal, called 2-Round Public Key System with S Boxes, or 2R, is based on the difficulty of decomposing the structure of several rounds of unknown linear transformations and S boxes. This difficulty is due to the difficulty of decomposing compositions of multivariate binary functions. In this paper we present a novel attack which breaks the 64-bit block variant with complexity about 230 steps, and the more secure 128-bit blocks variant with complexity about 260 steps. It is interesting to note that this cryptanalysis uses only the ciphertexts of selected plaintexts, and does not analyze the details of the supplied encryption code.
Chapter PDF
Similar content being viewed by others
References
W. Diffie, M. E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, Vol. 22, No. 6, Nov. 1976.
Tsutomu Matsumoto, Hideki Imai, Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT’88, pp. 419–453, 1988.
H. Ong, C. P. Schnorr, Adi Shamir, Efficient Signature Schemes Based on Polynomial Equations, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO’84, pp. 37–46, 1984.
Jacques Patarin, Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO’95, pp. 248–261, 1995.
Jacques Patarin, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT’96, pp. 33–48, 1996.
Jacques Patarin, Asymmetric Cryptography with a Hidden Monomial, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO’96, pp. 45–60, 1996.
Jacques Patarin, Louis Goubin, Asymmetric Cryptography with S Boxes, proceedings of ICICS’97, Lecture Notes in Computer Science 1334, pp. 369–380, 1997.
John M. Pollard, Claus P. Schnorr, An Efficient Solution to the Congruence x 2 + ky 2 = m(mod n), IEEE Transactions on Information Theory, Vol. 33, No. 5, 1987.
Adi Shamir, Efficient Signature Schemes Based on Birational Permutations, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO’93, pp. 1–12, 1993.
Serge Vaudenay, Jacques Stern, Don Coppersmith, Attacks on the Birational Permutation Signature Schemes, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO’93, pp. 435–443, 1993.
Ding-Feng Ye, Kwok-Yan Lam, Zong-Duo Dai, Cryptanalysis of “2R” Schemes, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO’99, pp. 315–325, 1999.
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
Biham, E. (2000). Cryptanalysis of Patarin’s 2-Round Public Key System with S Boxes (2R). 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_28
Download citation
DOI: https://doi.org/10.1007/3-540-45539-6_28
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