Abstract
In 2006, the inventors of TRMC public key cryptosystem proposed a new variant of TRMC, TRMC-4, which can resist the existing attack, in particular, the Joux et al attack. In this paper, we show that the new version is vulnerable to attack via the linearization equations (LE) method. For any given valid ciphertext and its corresponding TRMC-4 public key, we can derive the corresponding plaintext within 224 \(\mathbb{F}_{2^8}\)-operations, after performing once for the public key a computation of complexity less than 234. Our results are confirmed by computer experiments.
Chapter PDF
Similar content being viewed by others
Keywords
References
Ding, J., Hodges, T.: Cryptanalysis of an Implementation Scheme of TTM. J. Algebra Appl., 273–282 (2004), http://eprint.iacr.org/2003/084
Ding, J., Schmidt, D.: The new TTM implementation is not secure. In: Niederreiter, H., Feng, K.Q., Xing, C.P. (eds.) Proceedings of International Workshop on Coding, Cryptography and Combinatorics (CCC 2003), pp. 106–121 (2003)
Goubin, L., Courtois, N.: Cryptanalysis of the TTM cryptosystem. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 44–57. Springer, Heidelberg (2000)
Joux, A., Kunz-Jacques, S., Muller, F., Ricordel, P.-M.: Cryptanalysis of the Tractable Rational Map Cryptosystem. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 258–274. Springer, Heidelberg (2005)
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)
Moh, T.: A fast public key system with signature and master key functions. Lecture Notes at EE department of Stanford University (May 1999), http://www.usdsi.com/ttm.html
Nie, X., Hu, L., Li, J., Updegrove, C., Ding, J.: Breaking a New Instance of TTM Cryptosystems. In: Zhou, J., Yung, M., Bao, F. (eds.) ACNS 2006. LNCS, vol. 3989, pp. 210–225. Springer, Heidelberg (2006)
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)
Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5), 1484–1509 (1997)
Wang, L., Chang, F.: Tractable Rational Map Cryptosystem, available at http://eprint.iacr.org/2004/046 (revised on February 3, 2006)
Wolf, C.: Multivariate Quadratic Polynomials in Public Key Cryptography. Cryptology ePrint Archive, Report 2005/393 (2005), available at http://eprint.iacr.org/
Yang, B.-Y., Chen, J.-M.: Building Secure Tame-like Multivariate Public-Key Cryptosystems: The New TTS. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 518–531. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Nie, X., Hu, L., Ding, J., Li, J., Wagner, J. (2007). Cryptanalysis of the TRMC-4 Public Key Cryptosystem. In: Katz, J., Yung, M. (eds) Applied Cryptography and Network Security. ACNS 2007. Lecture Notes in Computer Science, vol 4521. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72738-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-72738-5_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72737-8
Online ISBN: 978-3-540-72738-5
eBook Packages: Computer ScienceComputer Science (R0)