Open Access
Issue
Published:
*15 October 2018*

Keywords:

cryptanalysis, post-quantum cryptography, multivariate public key cryptosystems, morphism ofpolynomials problem
Cite this article:

Chen J, Tan CH, Li aX.
Practical Cryptanalysis of a Public Key Cryptosystem Based on the Morphism of Polynomials Problem.
Tsinghua Science and Technology,
2018, 23(6): 671-679.
https://doi.org/10.26599/TST.2018.9010028
Download citation

416

Views

14

Downloads

Citations

6

Crossref

N/A

WoS

7

Scopus

0

CSCD

Multivariate Public Key Cryptography (MPKC) has intensively and rapidly developed during the past three decades. MPKC is a promising candidate for post-quantum cryptography. However, designing it is universally regarded as a difficult task to design a secure MPKC foundation scheme, such as an encryption scheme and key exchange scheme. In this work, we investigate the security of a new public key cryptosystem that is based on the Morphism of Polynomials (MP). The public key cryptosystem proposed by Wang et al. (Wuhan University, China) comprises a key exchange scheme and encryption scheme. Its security can be provably reduced to the hardness of solving a new difficult problem, namely, the Decisional Multivariate Diffie Hellman (DMDH) problem. This problem is a variant of the MP problem, which is difficult to solve by random systems. We present a proposition that reduces the DMDH problem to an easy example of the MP problem. Then, we propose an efficient algorithm for the Key Recover Attack (KRA) on the schemes of the public key cryptosystem. In practice, we are able to entirely break the cryptosystem’s claimed parameter of 96 security levels in less than 17.252 s. Furthermore, we show that finding parameters that yield a secure and practical scheme is impossible.

menu

Abstract

Full text

Outline

About this article

Multivariate Public Key Cryptography (MPKC) has intensively and rapidly developed during the past three decades. MPKC is a promising candidate for post-quantum cryptography. However, designing it is universally regarded as a difficult task to design a secure MPKC foundation scheme, such as an encryption scheme and key exchange scheme. In this work, we investigate the security of a new public key cryptosystem that is based on the Morphism of Polynomials (MP). The public key cryptosystem proposed by Wang et al. (Wuhan University, China) comprises a key exchange scheme and encryption scheme. Its security can be provably reduced to the hardness of solving a new difficult problem, namely, the Decisional Multivariate Diffie Hellman (DMDH) problem. This problem is a variant of the MP problem, which is difficult to solve by random systems. We present a proposition that reduces the DMDH problem to an easy example of the MP problem. Then, we propose an efficient algorithm for the Key Recover Attack (KRA) on the schemes of the public key cryptosystem. In practice, we are able to entirely break the cryptosystem’s claimed parameter of 96 security levels in less than 17.252 s. Furthermore, we show that finding parameters that yield a secure and practical scheme is impossible.

[1]

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

[2]

Lin B. H., Pei Y. K., Yin L. G., and Lu J. H., Design and efficient hardware implementation schemes for Non-Quasi-Cyclic LDPC codes, *Tsinghua Sci. Technol*., vol. 22, no. 1, pp. 92–103, 2017.

[3]

Chen J. H., Tang S. H., He D. J., and Tan Y., Online/offline signature based on uov in wireless sensor networks, *Wirel. Networks*, vol. 23, no. 6, pp. 1719–1730, 2017.

[4]

Matsumoto T. and Imai H., Public quadratic polynomial-tuples for efficient signature-verification and message-encryption, in *Advances in Cryptology-EUROCRYPT 98*, Barstow D.,Brauer W.,Hansen P. B.,Gries D.,Luckham D.,Moler C.,Pnueli A.,Seegmüller G.,Stoer J.,Wirth N., et al., eds. Springer, vol. 330, pp. 419–453, 1988.

[5]

Patarin J., The oil and vinegar signature scheme, in the Dagstuhl Workshop on Cryptography, 1997.

[6]

Tao C., Diene A., Tang S., and Ding J., Simple matrix scheme for encryption, in Proc. 5th Int. Post-Quantum Cryptography, Waterloo, Canada, 2013, pp. 231–242.

[7]

Porras J., Baena J., and Ding J., Zhfe, a new multivariate public key encryption scheme, in Proc. 6th Int. Post-Quantum Cryptography, Waterloo, Canada, 2014, pp. 229–245.

[8]

Zhang W. B. and Tan C. H., On the security and key generation of the ZHFE encryption scheme, in Proc. 11th Int. Workshop on Security, Tokyo, Japan, 2016, pp. 289–304.

[9]

Kipnis A., Patarin J., and Goubin L., Unbalanced oil and vinegar signature schemes, in *Advances in Cryptology-EUROCRYPT 99*, Stern J., ed. Springer, pp. 206–222, 1999.

[10]

Ding J. and Schmidt D., Rainbow—A new multivariable polynomial signature scheme, in *Applied Cryptography and Network Security*, Ioannidis J.,Keromytis A.,and Yung M., eds. Springer, 2005, pp. 164–175.

[11]

Patarin J., Courtois N., and Goubin, Quartz L., 128-bit long digital signatures, in Proc. Cryptographer’s Track at RSA Conf. San Francisco, CA, USA, 2001, pp. 282–297.

[12]

Petzoldt A., Chen M. S., Yang B. Y., Tao C. D., and Ding J. T., Design principles for HFEv-based multivariate signature schemes, in Proc. 21st Int. Conf. on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, 2015, pp. 311–334.

[13]

Chen M. S., Hülsing A., Rijneveld J., Samardjiska S., and Schwabe P., From 5-pass MQ-based identification to MQ-based signatures, in Proc. 22nd Int. Conf. on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016, pp. 135–165.

[14]

Chen J. H., Tang S. H., and Zhang X. L., HS-sign: A security enhanced UOV signature scheme based on hyper-sphere, *KSII Trans. Int. Inf. Syst*., vol. 11, no. 6, pp. 3166–3187, 2017.

[15]

Courtois N. T., Generic attacks and the security of Quartz, in *Public Key Cryptography 2003*, Desmedt Y. G., ed. Springer, 2002, pp. 351–364.

[16]

Bulygin S., Petzoldt A., and Buchmann J., Towards provable security of the unbalanced oil and vinegar signature scheme under direct attacks, in *Progress in Cryptology–INDOCRYPT 2010*, Gong G. and Gupta K. C.,eds. Springer, 2010, pp. 17–32.

[17]

Sakumoto K., Shirai T., and Hiwatari H., On provable security of UOV and HFE signature schemes against chosen-message attack, in *Post-Quantum Cryptography*, Yang B. Y., ed. Springer, 2011, pp. 68–82.

[18]

Bellare M. and Rogaway P., The exact security of digital signatures—How to sign with RSA and Rabin, in *Advances in Cryptology-EUROCRYPT’96*, Maurer U., ed. Springer, pp. 399–416, 1996.

[19]

Sakumoto K., Shirai T., and Hiwatari H., Public-key identification schemes based on multivariate quadratic polynomials, in *Advances in Cryptology–CRYPTO 2011*, Rogaway P., ed. Springer, 2011, pp. 706–723.

[20]

Liu J. H., Fan A. W., Jia J. W., Wang H. G., Zhang H. Z., and Mao S. W., Cryptanalysis of public key cryptosystems based on non-abelian factorization problems, *Tsinghua Sci. Technol*., vol. 21, no. 3, pp. 345–351, 2016.

[21]

Wang H. Z., Zhang H. G., Mao S. W., Wu W. Q., and Zhang L. Q., New public-key cryptosystem based on the morphism of polynomials problem, *Tsinghua Sci. Technol*., vol. 21, no. 3, pp. 302–311, 2016.

[22]

Patarin J. and Goubin L., Trapdoor one-way permutations and multivariate polynomials, in *Information and Communications Security*, Patarin J. and Coubin L.,eds. Springer, 1997, pp. 356–368.

[23]

Patarin J., Goubin L., and Courtois N., Improved algorithms for isomorphisms of polynomials, in *Advances in Cryptology–EUROCRYPT 1998*, Springer, 1998, pp. 184–200.

[24]

Courtois N., Klimov A., Patarin J., and Shamir A., Efficient algorithms for solving overdefined systems of multivariate polynomial equations, in *Advances in Cryptology–EUROCRYPT 2000*, Preneel B., ed. Springer, pp. 392–407, 2000.

[25]

Faugére J. C., A new efficient algorithm for computing Gröbner bases (F4), *J. Pure Appl. Algebra*, vol. 139, nos. 1–3, pp. 61–88, 1999.

[26]

Faugère J. C., A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), in Proc. Int. Symp. on Symbolic and Algebraic Computation, New York, NY, USA, pp. 75–83, 2002.

[27]

Bettale L., Faugère J. C., and Perret L., Hybrid approach for solving multivariate systems over finite fields, *J. Math. Cryptol*., vol. 3, no. 3, pp. 177–197, 2009.

[28]

Bosma W., Cannon J., and Playoust C., The Magma algebra system I: The user language, *J. Symbol. Computat*., vol. 24, nos. 3 & 4, pp. 235–265, 1997.

Publication history

Copyright

Rights and permissions

Received: 26 May 2017

Revised: 07 November 2017

Accepted: 14 November 2017

Published:
15 October 2018

Issue date: December 2018

© The authors 2018