Abstract
In this paper, we present the cryptanalysis of a public key scheme based on a system of multivariate polynomial equations, the “tractable rational map” cryptosystem. We show combinatorial weaknesses of the cryptosystem, and introduce a variant of the XL resolution algorithm, the Linear Method, which is able to leverage these weaknesses to invert in short time the trapdoor one-way function defined by the cipher using only the public key, and even rebuild a private key. We also interpret the behavior of the Linear Method on random instances of the scheme, and show that various generalizations of the cipher, as well as an increase of the security parameter, cannot lead to a secure scheme.
Chapter PDF
Similar content being viewed by others
Keywords
References
Adams, W., Loustaunau, P.: An introduction to Gröbner Bases. Graduate Studies in Mathematics, vol. 3. American Mathematical Society, Providence (1994)
Wang, L., Chang, F.: Tractable Rational Map Cryptosystem. Cryptology ePrint archive, Report 2004/046, http://eprint.iacr.org
Faugére, J.-C.: A New Efficient Algorithm for Computing Gröbner Bases without reduction to zero (F 5). In: Mora, T. (ed.) ISSAC 2002, pp. 75–83 (2002)
Faugére, J.-C.: Report on a Successful Attack of HFE Challenge 1 with Gröbner Basis Algorithm F5/2. Announcement on sci.crypt newsgroup, April 19 (2002)
Faugére, J.-C.: A New Efficient Algorithm for Computing Gröbner Bases (F 4). Journal of Pure and Applied Algebra 139(1-3), 61–88 (1999)
Matsumoto, T., Imai, H.: Public Quadratic Polynomial-tuples for Efficient Signature Verification and Message Encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988)
Faugère, J.-C., Joux, A.: Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003)
Kipnis, A., Shamir, A.: Cryptanalysis of the HFE Public-key Cryptosystem. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 19–30. Springer, Heidelberg (1999)
Lazard, D.: Gröbner Basis, Gaussian Elimination and Resolution of Systems of Algebraic Equations. In: van Hulzen, J.A. (ed.) ISSAC 1983 and EUROCAL 1983. LNCS, vol. 162, pp. 146–156. Springer, Heidelberg (1983)
The magma home page, http://www.maths.usyd.edu.au/u/magma .
Patarin, J., Courtois, N., Klimov, A., Shamir, A.: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In: Preneel, B. (ed.) Eurocrypt 2000. LNCS, vol. 180, pp. 392–407. Springer, Heidelberg (2000)
Patarin, J., Courtois, N., Goubin, L.: Improved Algorithms for Isomorphisms of Polynomials. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 184–200. Springer, Heidelberg (1998)
Patarin, J., Courtois, N., Goubin, L.: Flash, a Fast Multivariate Signature Algorithm. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 298–307. Springer, Heidelberg (2001)
Patarin, J.: Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’ 88. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248–261. Springer, Heidelberg (1995)
Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Joux, A., Kunz-Jacques, S., Muller, F., Ricordel, PM. (2005). Cryptanalysis of the Tractable Rational Map Cryptosystem. In: Vaudenay, S. (eds) Public Key Cryptography - PKC 2005. PKC 2005. Lecture Notes in Computer Science, vol 3386. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30580-4_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-30580-4_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24454-7
Online ISBN: 978-3-540-30580-4
eBook Packages: Computer ScienceComputer Science (R0)