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

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

May 2016, 10(2): 221-228. doi: 10.3934/amc.2016002

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

Keisuke Hakuta ^1, , Hisayoshi Sato ^2, and Tsuyoshi Takagi ^3,

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

Received March 2013 Published April 2016

Abstract
Related Papers

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: tame automorphism, Matsumoto-Imai cryptosystem, triangular transformation method, affine algebraic geometry., Multivariate public key cryptosystem.

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

Citation: Keisuke Hakuta, Hisayoshi Sato, Tsuyoshi Takagi. On tameness of Matsumoto-Imai central maps in three variables over the finite field $\mathbb F_2$. Advances in Mathematics of Communications, 2016, 10 (2) : 221-228. doi: 10.3934/amc.2016002

References:

[1]	J.-M. Chen and T. T. Moh, On the Goubin-Courtois attack on TTM,, available at , ().
[2]	N. Courtois, The security of hidden field equations (HFE),, in Progr. Crypt., (2001), 266. 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. doi: 10.1142/S0219498804000861.
[5]	J. Ding and D. Schmidt, The new TTM implementation is not secure,, in Workshop Coding Crypt. Combin., (2004), 113.
[6]	V. Dubois, P.-A. Fouque, A. Shamir and J. Stern, Practical cryptanalysis of SFLASH,, in Adv. Crypt. - CRYPTO 2007, (2007), 1. 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, (2007), 264. doi: 10.1007/978-3-540-72540-4_15.
[8]	A. van den Essen, Polynomial Automorphisms and the Jacobian Conjecture,, Birkhauser Verlag, (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, (1979).
[10]	L. Goubin and N. Courtois, Cryptanalysis of the TTM cryptosystem,, in Adv. Crypt. - ASIACRYPT 2000, (2000), 44. doi: 10.1007/3-540-44448-3_4.
[11]	E.-M. G. M. Hubbers, Nilpotent Jacobians,, Ph.D thesis, (1998).
[12]	H. W. E. Jung, Über ganze birationale transformationen der ebene,, J. Reine Angew. Math., 184 (1942), 161.
[13]	A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem,, in Adv. Crypt. - CRYPTO '99, (1999), 19. 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. doi: 10.1112/S0010437X07003399.
[15]	W. van der Kulk, On polynomial rings in two variables,, Nieuw Archief voor Wiskunde, 3 (1953), 33.
[16]	D. Lin, J.-C. Faugere, L. Perret and T. Wang, On enumeration of polynomial equivalence classes and their application to MPKC,, available at , (). 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, (1988), 419. doi: 10.1007/3-540-45961-8_39.
[18]	S. Maubach, Polynomial automorphisms over finite fields,, Serdica Math. J., 27 (2001), 343.
[19]	T. T. Moh, A fast public key system with signature and master key functions,, Comm. Algebra, 27 (1999), 2207. doi: 10.1080/00927879908826559.
[20]	T. T. Moh, An application of algebraic geometry to encryption: tame transformation method,, Rev. Mat. Iberoamericana, 19 (2003), 667. 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 , ().
[22]	M. Nagata, On Automorphism Group of $k[x, y]$,, Kinokuniya, (1972).
[23]	J. Patarin, Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt '88,, in Adv. Crypt. - CRYPTO '95, (1995), 248. 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, (1996), 33.
[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. 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*, (1998), 35.
[28]	J. Patarin, N. Courtois and L. Goubin, FLASH, a fast multivariate signature algorithm,, in Progr. Crypt., (2001), 297. 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, (1997), 369.
[30]	K. Rusek, Polynomial Automorphisms,, Preprint 456, (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. 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. 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., (1994), 124. doi: 10.1109/SFCS.1994.365700.
[34]	M. K. Smith, Stably tame automorphisms,, J. Pure Appl. Algebra, 58 (1989), 209. doi: 10.1016/0022-4049(89)90158-8.
[35]	S. Spodzieja, On the Nagata automorphism,, Univ. Iagell. Acta Math., 1298 (2007), 131.

show all references

References:

[1]	J.-M. Chen and T. T. Moh, On the Goubin-Courtois attack on TTM,, available at , ().
[2]	N. Courtois, The security of hidden field equations (HFE),, in Progr. Crypt., (2001), 266. 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. doi: 10.1142/S0219498804000861.
[5]	J. Ding and D. Schmidt, The new TTM implementation is not secure,, in Workshop Coding Crypt. Combin., (2004), 113.
[6]	V. Dubois, P.-A. Fouque, A. Shamir and J. Stern, Practical cryptanalysis of SFLASH,, in Adv. Crypt. - CRYPTO 2007, (2007), 1. 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, (2007), 264. doi: 10.1007/978-3-540-72540-4_15.
[8]	A. van den Essen, Polynomial Automorphisms and the Jacobian Conjecture,, Birkhauser Verlag, (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, (1979).
[10]	L. Goubin and N. Courtois, Cryptanalysis of the TTM cryptosystem,, in Adv. Crypt. - ASIACRYPT 2000, (2000), 44. doi: 10.1007/3-540-44448-3_4.
[11]	E.-M. G. M. Hubbers, Nilpotent Jacobians,, Ph.D thesis, (1998).
[12]	H. W. E. Jung, Über ganze birationale transformationen der ebene,, J. Reine Angew. Math., 184 (1942), 161.
[13]	A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem,, in Adv. Crypt. - CRYPTO '99, (1999), 19. 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. doi: 10.1112/S0010437X07003399.
[15]	W. van der Kulk, On polynomial rings in two variables,, Nieuw Archief voor Wiskunde, 3 (1953), 33.
[16]	D. Lin, J.-C. Faugere, L. Perret and T. Wang, On enumeration of polynomial equivalence classes and their application to MPKC,, available at , (). 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, (1988), 419. doi: 10.1007/3-540-45961-8_39.
[18]	S. Maubach, Polynomial automorphisms over finite fields,, Serdica Math. J., 27 (2001), 343.
[19]	T. T. Moh, A fast public key system with signature and master key functions,, Comm. Algebra, 27 (1999), 2207. doi: 10.1080/00927879908826559.
[20]	T. T. Moh, An application of algebraic geometry to encryption: tame transformation method,, Rev. Mat. Iberoamericana, 19 (2003), 667. 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 , ().
[22]	M. Nagata, On Automorphism Group of $k[x, y]$,, Kinokuniya, (1972).
[23]	J. Patarin, Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt '88,, in Adv. Crypt. - CRYPTO '95, (1995), 248. 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, (1996), 33.
[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. 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*, (1998), 35.
[28]	J. Patarin, N. Courtois and L. Goubin, FLASH, a fast multivariate signature algorithm,, in Progr. Crypt., (2001), 297. 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, (1997), 369.
[30]	K. Rusek, Polynomial Automorphisms,, Preprint 456, (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. 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. 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., (1994), 124. doi: 10.1109/SFCS.1994.365700.
[34]	M. K. Smith, Stably tame automorphisms,, J. Pure Appl. Algebra, 58 (1989), 209. doi: 10.1016/0022-4049(89)90158-8.
[35]	S. Spodzieja, On the Nagata automorphism,, Univ. Iagell. Acta Math., 1298 (2007), 131.

[1]	Sikhar Patranabis, Debdeep Mukhopadhyay. Identity-based key aggregate cryptosystem from multilinear maps. Advances in Mathematics of Communications, 2019, 13 (4) : 759-778. doi: 10.3934/amc.2019044
[2]	Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023
[3]	Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281
[4]	Joan-Josep Climent, Elisa Gorla, Joachim Rosenthal. Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications, 2007, 1 (1) : 1-11. doi: 10.3934/amc.2007.1.1
[5]	Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.
[6]	Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489
[7]	Oğul Esen, Partha Guha. On the geometry of the Schmidt-Legendre transformation. Journal of Geometric Mechanics, 2018, 10 (3) : 251-291. doi: 10.3934/jgm.2018010
[8]	Joan-Josep Climent, Juan Antonio López-Ramos. Public key protocols over the ring $E_{p}^{(m)}$. Advances in Mathematics of Communications, 2016, 10 (4) : 861-870. doi: 10.3934/amc.2016046
[9]	Alex L Castro, Wyatt Howard, Corey Shanbrom. Bridges between subriemannian geometry and algebraic geometry: Now and then. Conference Publications, 2015, 2015 (special) : 239-247. doi: 10.3934/proc.2015.0239
[10]	Gusein Sh. Guseinov. Spectral method for deriving multivariate Poisson summation formulae. Communications on Pure & Applied Analysis, 2013, 12 (1) : 359-373. doi: 10.3934/cpaa.2013.12.359
[11]	Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215
[12]	Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117
[13]	Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485
[14]	Qilong Zhai, Ran Zhang. Lower and upper bounds of Laplacian eigenvalue problem by weak Galerkin method on triangular meshes. Discrete & Continuous Dynamical Systems - B, 2019, 24 (1) : 403-413. doi: 10.3934/dcdsb.2018091
[15]	Jinkui Liu, Shengjie Li. Multivariate spectral DY-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2017, 13 (1) : 283-295. doi: 10.3934/jimo.2016017
[16]	Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507
[17]	Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[18]	Christian Pötzsche. Dichotomy spectra of triangular equations. Discrete & Continuous Dynamical Systems - A, 2016, 36 (1) : 423-450. doi: 10.3934/dcds.2016.36.423
[19]	Drew Fudenberg, David K. Levine. Tail probabilities for triangular arrays. Journal of Dynamics & Games, 2014, 1 (1) : 45-56. doi: 10.3934/jdg.2014.1.45
[20]	Graham W. Alldredge, Ruo Li, Weiming Li. Approximating the $M_2$ method by the extended quadrature method of moments for radiative transfer in slab geometry. Kinetic & Related Models, 2016, 9 (2) : 237-249. doi: 10.3934/krm.2016.9.237

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences