American Institute of Mathematical Sciences

Advanced
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

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

[2]

N. Courtois, The security of hidden field equations (HFE),, in Progr. Crypt., (2001), 266.  doi: 10.1007/3-540-45353-9_20.  Google Scholar

[3]

J. Ding, J. E. Gower and D. S. Schmidt, Multivariate Public Key Cryptosystems,, Springer, (2006).   Google Scholar

[4]

J. Ding and T. Hodges, Cryptanalysis of an implementation scheme of TTM,, J. Algebra Appl., 3 (2004), 273.  doi: 10.1142/S0219498804000861.  Google Scholar

[5]

J. Ding and D. Schmidt, The new TTM implementation is not secure,, in Workshop Coding Crypt. Combin., (2004), 113.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

A. van den Essen, Polynomial Automorphisms and the Jacobian Conjecture,, Birkhauser Verlag, (2000).  doi: 10.1007/978-3-0348-8440-2.  Google Scholar

[9]

M. R. Garey and D. S. Johnson, Computer and Intractability: A Guide to the Theory of NP-completeness,, Freeman, (1979).   Google Scholar

[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.  Google Scholar

[11]

E.-M. G. M. Hubbers, Nilpotent Jacobians,, Ph.D thesis, (1998).   Google Scholar

[12]

H. W. E. Jung, Über ganze birationale transformationen der ebene,, J. Reine Angew. Math., 184 (1942), 161.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

W. van der Kulk, On polynomial rings in two variables,, Nieuw Archief voor Wiskunde, 3 (1953), 33.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

S. Maubach, Polynomial automorphisms over finite fields,, Serdica Math. J., 27 (2001), 343.   Google Scholar

[19]

T. T. Moh, A fast public key system with signature and master key functions,, Comm. Algebra, 27 (1999), 2207.  doi: 10.1080/00927879908826559.  Google Scholar

[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.  Google Scholar

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

[22]

M. Nagata, On Automorphism Group of $k[x, y]$,, Kinokuniya, (1972).   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[25]

J. Patarin, The oil and vinegar signature scheme,, in Dagstuhl Workshop on Cryptography, (1997).   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[29]

J. Patarin and L. Goubin, Asymmetric cryptography with S-boxes,, in 1st Int. Conf. Inf. Sec. Crypt. - ICISC '97, (1997), 369.   Google Scholar

[30]

K. Rusek, Polynomial Automorphisms,, Preprint 456, (1989).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[34]

M. K. Smith, Stably tame automorphisms,, J. Pure Appl. Algebra, 58 (1989), 209.  doi: 10.1016/0022-4049(89)90158-8.  Google Scholar

[35]

S. Spodzieja, On the Nagata automorphism,, Univ. Iagell. Acta Math., 1298 (2007), 131.   Google Scholar

show all references

References:
[1]

J.-M. Chen and T. T. Moh, On the Goubin-Courtois attack on TTM,, available at , ().   Google Scholar

[2]

N. Courtois, The security of hidden field equations (HFE),, in Progr. Crypt., (2001), 266.  doi: 10.1007/3-540-45353-9_20.  Google Scholar

[3]

J. Ding, J. E. Gower and D. S. Schmidt, Multivariate Public Key Cryptosystems,, Springer, (2006).   Google Scholar

[4]

J. Ding and T. Hodges, Cryptanalysis of an implementation scheme of TTM,, J. Algebra Appl., 3 (2004), 273.  doi: 10.1142/S0219498804000861.  Google Scholar

[5]

J. Ding and D. Schmidt, The new TTM implementation is not secure,, in Workshop Coding Crypt. Combin., (2004), 113.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

A. van den Essen, Polynomial Automorphisms and the Jacobian Conjecture,, Birkhauser Verlag, (2000).  doi: 10.1007/978-3-0348-8440-2.  Google Scholar

[9]

M. R. Garey and D. S. Johnson, Computer and Intractability: A Guide to the Theory of NP-completeness,, Freeman, (1979).   Google Scholar

[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.  Google Scholar

[11]

E.-M. G. M. Hubbers, Nilpotent Jacobians,, Ph.D thesis, (1998).   Google Scholar

[12]

H. W. E. Jung, Über ganze birationale transformationen der ebene,, J. Reine Angew. Math., 184 (1942), 161.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

W. van der Kulk, On polynomial rings in two variables,, Nieuw Archief voor Wiskunde, 3 (1953), 33.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

S. Maubach, Polynomial automorphisms over finite fields,, Serdica Math. J., 27 (2001), 343.   Google Scholar

[19]

T. T. Moh, A fast public key system with signature and master key functions,, Comm. Algebra, 27 (1999), 2207.  doi: 10.1080/00927879908826559.  Google Scholar

[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.  Google Scholar

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

[22]

M. Nagata, On Automorphism Group of $k[x, y]$,, Kinokuniya, (1972).   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[25]

J. Patarin, The oil and vinegar signature scheme,, in Dagstuhl Workshop on Cryptography, (1997).   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[29]

J. Patarin and L. Goubin, Asymmetric cryptography with S-boxes,, in 1st Int. Conf. Inf. Sec. Crypt. - ICISC '97, (1997), 369.   Google Scholar

[30]

K. Rusek, Polynomial Automorphisms,, Preprint 456, (1989).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[34]

M. K. Smith, Stably tame automorphisms,, J. Pure Appl. Algebra, 58 (1989), 209.  doi: 10.1016/0022-4049(89)90158-8.  Google Scholar

[35]

S. Spodzieja, On the Nagata automorphism,, Univ. Iagell. Acta Math., 1298 (2007), 131.   Google Scholar

[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]

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, 2020  doi: 10.3934/amc.2020076
[10]

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
[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]

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
[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]

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
[15]

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
[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]

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
[18]

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
[19]

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
[20]

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

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (60)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences