On tameness of Matsumoto-Imai central maps in three variables over the finite field $\mathbb F_2$

Keisuke  Hakuta; Hisayoshi  Sato; Tsuyoshi  Takagi

doi:10.3934/amc.2016002

Article Contents

2016, Volume 10, Issue 2: 221-228. Doi: 10.3934/amc.2016002

This issue Previous Article On codes over FFN$(1,q)$-projective varieties Next Article On the ideal associated to a linear code

On tameness of Matsumoto-Imai central maps in three variables over the finite field $\mathbb F_2$

1.
Interdisciplinary Graduate School of Science and Engineering, Shimane University, 1060 Nishikawatsu-cho, Matsue-shi, Shimane 690-8504
2.
Security Research Department, Center of Technology Innovation-Systems Engineering, Hitachi, Ltd., 292, Yoshida-cho, Totsuka-ku, Yokohama-shi, Kanagawa 244-0817
3.
Institute of Mathematics for Industry, Kyushu University, 744, Motooka, Nishi-ku, Fukuoka-shi, Fukuoka 819-0395

Received: February 28, 2013

Published: April 2016

Abstract Related Papers Cited by

Abstract

Triangular transformation method (TTM) is one of the multivariate public key cryptosystems (MPKC) based on the intractability of tame decomposition problem. In TTM, a special class of tame automorphisms are used to construct encryption schemes. However, because of the specificity of such tame automorphisms, it is important to evaluate the computational complexity of the tame decomposition problem for secure use of MPKC. In this paper, as the first step for security evaluations, we focus on Matsumoto-Imai cryptosystems. We shall prove that the Matsumoto-Imai central maps in three variables over $\mathbb{F}_{2}$ is tame, and we describe the tame decompositions of the Matsumoto-Imai central maps.

Keywords:

Mathematics Subject Classification: Primary: 94A60, 14R10; Secondary: 12Y05, 12D05, 11Y16, 13P05.

Citation:

Related Papers

Cited by

References

[1]	J.-M. Chen and T. T. Moh, On the Goubin-Courtois attack on TTM, available at http://eprint.iacr.org/2001/072
[2]	N. Courtois, The security of hidden field equations (HFE), in Progr. Crypt., CT-RSA '01, Springer-Verlag, 2001, 266-281.doi: 10.1007/3-540-45353-9_20.
[3]	J. Ding, J. E. Gower and D. S. Schmidt, Multivariate Public Key Cryptosystems, Springer, 2006.
[4]	J. Ding and T. Hodges, Cryptanalysis of an implementation scheme of TTM, J. Algebra Appl., 3 (2004), 273-282.doi: 10.1142/S0219498804000861.
[5]	J. Ding and D. Schmidt, The new TTM implementation is not secure, in Workshop Coding Crypt. Combin., CCC2003, Birkhauser Verlag, 2004, 113-128.
[6]	V. Dubois, P.-A. Fouque, A. Shamir and J. Stern, Practical cryptanalysis of SFLASH, in Adv. Crypt. - CRYPTO 2007, Springer-Verlag, 2007, 1-12.doi: 10.1007/978-3-540-74143-5_1.
[7]	V. Dubois, P.-A. Fouque and J. Stern, Cryptanalysis of SFLASH with slightly modified parameters, in Adv. Crypt. - EUROCRYPT 2007, Springer-Verlag, 2007, 264-275.doi: 10.1007/978-3-540-72540-4_15.
[8]	A. van den Essen, Polynomial Automorphisms and the Jacobian Conjecture, Birkhauser Verlag, Basel, 2000.doi: 10.1007/978-3-0348-8440-2.
[9]	M. R. Garey and D. S. Johnson, Computer and Intractability: A Guide to the Theory of NP-completeness, Freeman, New York, 1979.
[10]	L. Goubin and N. Courtois, Cryptanalysis of the TTM cryptosystem, in Adv. Crypt. - ASIACRYPT 2000, Springer-Verlag, 2000, 44-57.doi: 10.1007/3-540-44448-3_4.
[11]	E.-M. G. M. Hubbers, Nilpotent Jacobians, Ph.D thesis, Univ. Nijmegen, 1998.
[12]	H. W. E. Jung, Über ganze birationale transformationen der ebene, J. Reine Angew. Math., 184 (1942), 161-174.
[13]	A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem, in Adv. Crypt. - CRYPTO '99, Springer-Verlag, 1999, 19-30.doi: 10.1007/3-540-48405-1_2.
[14]	T. Kishimoto, A new proof of the non-tameness of the Nagata automorphism from the point of view of the Sarkisov program, Compositio Math., 144 (2008), 963-977.doi: 10.1112/S0010437X07003399.
[15]	W. van der Kulk, On polynomial rings in two variables, Nieuw Archief voor Wiskunde, 3 (1953), 33-41.
[16]	D. Lin, J.-C. Faugere, L. Perret and T. Wang, On enumeration of polynomial equivalence classes and their application to MPKC, available at http://eprint.iacr.org/2011/055 doi: 10.1016/j.ffa.2011.09.001.
[17]	T. Matsumoto and H. Imai, Public quadratic polynominal-tuples for efficient signature-verification and message-encryption, in Adv. Crypt. - EUROCRYPT '88, Springer-Verlag, 1988, 419-453.doi: 10.1007/3-540-45961-8_39.
[18]	S. Maubach, Polynomial automorphisms over finite fields, Serdica Math. J., 27 (2001), 343-350.
[19]	T. T. Moh, A fast public key system with signature and master key functions, Comm. Algebra, 27 (1999), 2207-2222.doi: 10.1080/00927879908826559.
[20]	T. T. Moh, An application of algebraic geometry to encryption: tame transformation method, Rev. Mat. Iberoamericana, 19 (2003), 667-685.doi: 10.4171/RMI/364.
[21]	T. T. Moh, J.-M. Chen, and B.-Y. Yang, Building instances of TTM immune to the Goubin-Courtois attack and the Ding-Schmidt attack, available at http://eprint.iacr.org/2004/168
[22]	M. Nagata, On Automorphism Group of $k[x, y]$, Kinokuniya, Tokyo, 1972.
[23]	J. Patarin, Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt '88, in Adv. Crypt. - CRYPTO '95, Springer-Verlag, 1995, 248-261.doi: 10.1007/3-540-44750-4_20.
[24]	J. Patarin, Hidden field equations (HFE) and isomorphism of polynomials (IP): two new families of asymmetric algorithms, in Adv. Crypt. - EUROCRYPT '96, Springer-Verlag, 1996, 33-48.
[25]	J. Patarin, The oil and vinegar signature scheme, in Dagstuhl Workshop on Cryptography, 1997.
[26]	J. Patarin, Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt '88, Des. Codes Crypt., 20 (2000), 175-209.doi: 10.1023/A:1008341625464.
[27]	J. Patarin, N. Courtois and L. Goubin, $C_{-+}^{}$ and HM: variations around two schemes of T. Matsumoto and H. Imai, in Adv. Crypt. - ASIACRYPT '98*, Springer-Verlag, 1998, 35-50.
[28]	J. Patarin, N. Courtois and L. Goubin, FLASH, a fast multivariate signature algorithm, in Progr. Crypt., CT-RSA '01, Springer-Verlag, 2001, 297-307.doi: 10.1007/3-540-45353-9_22.
[29]	J. Patarin and L. Goubin, Asymmetric cryptography with S-boxes, in 1st Int. Conf. Inf. Sec. Crypt. - ICISC '97, Springer-Verlag, 1997, 369-380.
[30]	K. Rusek, Polynomial Automorphisms, Preprint 456, Inst. Math., Polish Acad. Sci., IMPAN, Warsaw, 1989.
[31]	I. P. Shestakov and U. U. Umirbaev, Poisson brackets and two-generated subalgebras of rings of polynomials, J. Amer. Math. Soc., 17 (2004), 181-196.doi: 10.1090/S0894-0347-03-00438-7.
[32]	I. P. Shestakov and U. U. Umirbaev, The tame and the wild automorphisms of polynomial rings in three variables, J. Amer. Math. Soc., 17 (2004), 197-227.doi: 10.1090/S0894-0347-03-00440-5.
[33]	P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in 35th Ann. Symp. Found. Comp. Sci., IEEE, 1994, 124-134.doi: 10.1109/SFCS.1994.365700.
[34]	M. K. Smith, Stably tame automorphisms, J. Pure Appl. Algebra, 58 (1989), 209-212.doi: 10.1016/0022-4049(89)90158-8.
[35]	S. Spodzieja, On the Nagata automorphism, Univ. Iagell. Acta Math., 1298 (2007), 131-136.