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

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

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., 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 , (). 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 , ().
[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.

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., 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 , (). 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 , ().
[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.

[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]	Shixiong Wang, Longjiang Qu, Chao Li, Shaojing Fu, Hao Chen. Finding small solutions of the equation $ \mathit{{Bx-Ay = z}} $ and its applications to cryptanalysis of the RSA cryptosystem. Advances in Mathematics of Communications, 2021, 15 (3) : 441-469. doi: 10.3934/amc.2020076
[9]	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
[10]	Yu-Chi Chen. Security analysis of public key encryption with filtered equality test. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021053
[11]	Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022031
[12]	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
[13]	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
[14]	Gusein Sh. Guseinov. Spectral method for deriving multivariate Poisson summation formulae. Communications on Pure and Applied Analysis, 2013, 12 (1) : 359-373. doi: 10.3934/cpaa.2013.12.359
[15]	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
[16]	Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial and Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117
[17]	Qilong Zhai, Ran Zhang. Lower and upper bounds of Laplacian eigenvalue problem by weak Galerkin method on triangular meshes. Discrete and Continuous Dynamical Systems - B, 2019, 24 (1) : 403-413. doi: 10.3934/dcdsb.2018091
[18]	Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507
[19]	Jinkui Liu, Shengjie Li. Multivariate spectral DY-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial and Management Optimization, 2017, 13 (1) : 283-295. doi: 10.3934/jimo.2016017
[20]	Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Keisuke Hakuta Hisayoshi Sato Tsuyoshi Takagi
on Google Scholar
Keisuke Hakuta Hisayoshi Sato Tsuyoshi Takagi

[Back to Top]