New Public-Key Cryptosystem Based on the Morphism of Polynomials Problem

Houzhen Wang; Huanguo Zhang; Shaowu Mao; Wanqing Wu; Liqiang Zhang

doi:10.1109/TST.2016.7488741

Tsinghua Science and Technology 2016, 21(3): 302-311 https://doi.org/10.1109/TST.2016.7488741

Open Access | Issue | Published: 13 June 2016

New Public-Key Cryptosystem Based on the Morphism of Polynomials Problem

Show Author's Information Hide Author's Information Houzhen Wang, Huanguo Zhang, Shaowu Mao, Wanqing Wu, Liqiang Zhang(

)

Computer School of Wuhan University, Wuhan

430079

China and the State Key Laboratory of Cryptology, Beijing 100878, China.

Keywords:

public key cryptosystem, key exchange, Multivariate Public Key Cryptography (MPKC), Morphism of Polynomials (MP) problem

Cite this article:

Wang H, Zhang H, Mao S, et al. New Public-Key Cryptosystem Based on the Morphism of Polynomials Problem. Tsinghua Science and Technology, 2016, 21(3): 302-311. https://doi.org/10.1109/TST.2016.7488741

Download citation

EndNote(RIS)

BibTeX

480

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

During the last two decades, there has been intensive and fast development in Multivariate Public Key Cryptography (MPKC), which is considered to be an important candidate for post-quantum cryptography. However, it is universally regarded as a difficult task, as in the Knapsack cryptosystems, to design a secure MPKC scheme (especially an encryption scheme) employing the existing trapdoor construction. In this paper, we propose a new key-exchange scheme and an MPKC scheme based on the Morphism of Polynomials (MP) problem. The security of the proposed schemes is provably reducible to the conjectured intractability of a new difficult problem, namely the Decisional Multivariate Diffie-Hellman (DMDH) problem derived from the MP problem. The proposed key agreement is one of several non-number-theory-based protocols, and is a candidate for use in the post-quantum era. More importantly, by slightly modifying the protocol, we offer an original approach to designing a secure MPKC scheme. Furthermore, the proposed encryption scheme achieves a good tradeoff between security and efficiency, and seems competitive with traditional MPKC schemes.

Full text

Abstract

Full text

Outline

About this article

New Public-Key Cryptosystem Based on the Morphism of Polynomials Problem

Show Author's information Hide Author's Information Houzhen Wang, Huanguo Zhang, Shaowu Mao, Wanqing Wu, Liqiang Zhang(

)

Computer School of Wuhan University, Wuhan

430079

China and the State Key Laboratory of Cryptology, Beijing 100878, China.

Abstract

Keywords: public key cryptosystem, key exchange, Multivariate Public Key Cryptography (MPKC), Morphism of Polynomials (MP) problem

References(39)

[1]

Diffie W. and Hellman M. E., New directions in cryptography, IEEE Trans. on Info. Theory, vol. 22, no. 6, pp. 644-654, 1976.

DOI Google Scholar

[2]

Law L., Menezes A., Qu M., Solinas J., and Vanstone S., An efficient protocol for authenticated key agreement, Designs, Codes and Cryptography, vol. 28, no. 2, pp. 119-134, 2003.

DOI Google Scholar

[3]

Hu K., Xue J., Hu C., Ma R., and Li Z., An improved ID-based group key agreement protocol, Tsinghua Science and Technology, vol. 19, no. 5, pp. 421-428, 2014.

DOI Google Scholar

[4]

Shor P. W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computer, vol. 26, no. 5, pp. 1484-1509, 1997.

DOI Google Scholar

[5]

Bernstein D. J., Buchmann J., and Dahmen E., Post-Quantum Cryptography. Springer-Verlag, 2009.

Google Scholar

[6]

Ding J. T., Gower J. E., and Schmidt D. S., Multivariate Public Key Cryptosystems. Springer-Verlag, 2006.

Google Scholar

[7]

Garey M. R. and Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.

Google Scholar

[8]

Patarin J. and Goubin L., Trapdoor one-way permutations and multivariate polynomials, in Proc. ICICS1997, 1997, pp. 356-368.

DOI

[9]

Berbain C., Gilbert H., and Patarin J., QUAD: A practical stream cipher with provable security, in Proc. EUROCRYPT2006, 2006, pp. 109-128.

DOI

[10]

Wang H. Z., Zhang H. G., and Wu Q. H., Design theory and method of multivariate hash function, SCIENCE CHINA Information Sciences, no. 10, pp. 1977-1987, 2010.

DOI Google Scholar

[11]

Sakumoto K., Shirai T., and Hiwatari H., Public-key identification schemes based on multivariate quadratic polynomials, in Proc. CRYPTO2011, 2011, pp. 706-723.

DOI

[12]

Billet O. and Gilles M. R., Cryptanalysis of the square cryptosystems, in Proc. ASIACRYPT 2009, 2009, pp. 451-468.

DOI

[13]

Dubois V., Fouque P. A., Shamir A., and Stern J., Practical cryptanalysis of SFLASH, in Proc. Crypto2007, 2007, pp. 1-12.

DOI

[14]

Goubin L. and Courtois N. T., Cryptanalysis of the TTM cryptosystem, in Proc. ASIACRYPT2000, 2000, pp. 44-57.

DOI

[15]

Tao C. D., Diene A., Tang S. H., and Ding J. T., A simple matrix scheme for encryption, in PQC2013, 2013, pp. 231-242.

DOI

[16]

Wang H. Z. and Zhang H. G., Extended multivariate public key cryptosystems with secure encrytion fuction, SCIENCE CHINA Information Sciences, no. 6, pp. 1161-1171, 2011.

DOI Google Scholar

[17]

Sakumoto K., Shirai T., and Hiwatari H., On provable security of UOV and HFE signature schemes against Chosen-Message attack, in Proc. PQC2011, 2011, pp. 68-82.

DOI

[18]

Anshel I., Anshel M., and Goldfeld D., An algebraic method for public-key cryptography, Math Research Letters, 1999, vol. 6, no. 3, pp. 287-291

DOI Google Scholar

[19]

Anshel I., Anshel M., and Goldfeld D., New key agreement protocols in braid group cryptography, in Proc. CT-RSA2001, 2001, pp. 1-15

DOI

[20]

Myasnikov A., Shpilrain V., and Ushakov A., A practical attack on a Braid group based cryptographic protocol, in Proc. Crypto2005, 2005, pp. 86-96.

DOI

[21]

Myasnikov A. and Ushakov A., Length based attack and Braid groups: Cryptanalysis of Anshel-Anshel-Goldfeld Key exchange protocol, in Proc. PKC2007, 2007, pp. 76-88

DOI

[22]

Ko K., Lee S., Cheon J., Han J., Kang J., and Park C., New pulic-key cryptosystem using Braid groups, in Proc. Crypto2000, 2000, pp. 166-183.

DOI

[23]

Cheon J. H. and Jun B., A polynomial time algorithm for the Braid Diffie-Hellman conjugacy problem, in Proc. Crypto2003, 2003, pp. 212-215.

DOI

[24]

Boucher D., Gaborit P., Geiselmann W., Ruatta O., and Ulmer F., Key exchange and encryption schemes based on non-commutative skew polynomials, in Proc. PQCrypto2010, 2010, pp. 126-141.

DOI

[25]

Dubois V. and Kammerer J. G., Cryptanalysis of cryptosystems based on non-commutative skew polynomials, in Proc. PKC 2011, 2011, pp. 459-472.

DOI

[26]

Bennett C. H. and Brassard G., An update on quantum cryptography, in Proc. CRYPTO1984, 1984, pp. 475-480.

DOI

[27]

Bennett C., Quantum cryptography using any two nonorthoganol states, Phys. Rev. Lett., vol. 68, no. 21, pp. 3121-3124, 1992.

DOI Google Scholar

[28]

Matsumoto T. and Imai H., Public quadratic polynomial-tuples for efficient signature verification and message encryption, in Proc. EUROCRYPT1988, 1988, pp. 419-453.

DOI

[29]

Patarin J., Hidden field equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms, in Proc. EUROCRYPT1996, 1996, pp. 33-48.

DOI

[30]

Bouillaguet C., Faugère J. C., Fouque P. A., and Perret L., Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem, in Porc. PKC2011, 2011, pp. 473-493.

DOI

[31]

Francoise L. and Ludovic F., Polynomial equivalence problems and applications to multivariate cryptosystems, in Proc. INDOCRYPT 2003, 2003, pp. 235-251.

DOI

[32]

Lin D., Faugère J. C., Perret L., and Wang T., On enumeration of polynomial equivalence classes and their application to MPKC, Finite Fields and Their Applications, vol. 18, no. 2, pp. 283-302, 2012.

DOI Google Scholar

[33]

Faugère J. C. and Perret L., Polynomial equivalence problems: Algorithmic and theoretical aspects, in Proc. EUROCRYPT2006, 2006, pp. 30-47.

DOI

[34]

Fouque P. A., Macario-Rat G., and Stern J., Key recovery on hidden monomial multivariate schemes, in Proc. EUROCRYPT2008, 2008, pp. 19-30.

DOI

[35]

Patarin J., Goubin L., and Courtois N., Improved algorithms for isomorphisms of polynomials, in Proc. EUROCRYPT1998, 1998, pp. 184-200.

DOI

[36]

Katz J. and Lindell Y., Introduction to Modern Cryptography. Chapman & Hall/CRC, 2007.

DOI Google Scholar

[37]

Courtois N. and Pieprzyk J., Cryptanalysis of block ciphers with overdefined systems of equations, in Proc. Asiacrypt 2002, 2002, pp. 267-287.

DOI

[38]

Jin H., Struction of matrices space exchangeable for given matrix, Mathematical Theory and Applications, vol. 21, no. 3, pp. 40-44, 2001.

Google Scholar

[39]

Akkar M. and Courtois, N, A fast and secure implementation of SFLASH, in Proc. PKC2003, 2003, pp. 267-278.

DOI

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 09 February 2016

Accepted: 07 March 2016

Published: 13 June 2016

Issue date: June 2016

Copyright

Acknowledgements

The authors would like to thank anonymous referees for their valuable comments. This work was supported by the National Natural Science Foundation of China (Nos. 61303212, 61303024, 61170080, 61501333, 61303024, and 61332019) and the Foundation of Science and Technology on Information Assurance Laboratory (No. KJ-14-002).