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]

Ville Salo, Ilkka Törmä. Recoding Lie algebraic subshifts. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 1005-1021. doi: 10.3934/dcds.2020307
[2]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
[3]

Jintai Ding, Zheng Zhang, Joshua Deaton. The singularity attack to the multivariate signature scheme HIMQ-3. Advances in Mathematics of Communications, 2021, 15 (1) : 65-72. doi: 10.3934/amc.2020043
[4]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065
[5]

Xinlin Cao, Huaian Diao, Jinhong Li. Some recent progress on inverse scattering problems within general polyhedral geometry. Electronic Research Archive, 2021, 29 (1) : 1753-1782. doi: 10.3934/era.2020090
[6]

Kerioui Nadjah, Abdelouahab Mohammed Salah. Stability and Hopf bifurcation of the coexistence equilibrium for a differential-algebraic biological economic system with predator harvesting. Electronic Research Archive, 2021, 29 (1) : 1641-1660. doi: 10.3934/era.2020084
[7]

Hongyan Guo. Automorphism group and twisted modules of the twisted Heisenberg-Virasoro vertex operator algebra. Electronic Research Archive, , () : -. doi: 10.3934/era.2021008
[8]

Tomáš Oberhuber, Tomáš Dytrych, Kristina D. Launey, Daniel Langr, Jerry P. Draayer. Transformation of a Nucleon-Nucleon potential operator into its SU(3) tensor form using GPUs. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1111-1122. doi: 10.3934/dcdss.2020383
[9]

Antoine Benoit. Weak well-posedness of hyperbolic boundary value problems in a strip: when instabilities do not reflect the geometry. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5475-5486. doi: 10.3934/cpaa.2020248
[10]

Yuanfen Xiao. Mean Li-Yorke chaotic set along polynomial sequence with full Hausdorff dimension for $ \beta $-transformation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 525-536. doi: 10.3934/dcds.2020267
[11]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[12]

Xiaoxiao Li, Yingjing Shi, Rui Li, Shida Cao. Energy management method for an unpowered landing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020180
[13]

Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095
[14]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[15]

Qing-Hu Hou, Yarong Wei. Telescoping method, summation formulas, and inversion pairs. Electronic Research Archive, , () : -. doi: 10.3934/era.2021007
[16]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[17]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[18]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[19]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[20]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences