An improved signature model of multivariate polynomial public key cryptosystem against key recovery attack

Xin Wang; Bo Yang; Xin Wang; Bo Yang

doi:10.3934/mbe.2019388

Mathematical Biosciences and Engineering

2019, Volume 16, Issue 6: 7734-7750. doi: 10.3934/mbe.2019388

Previous Article Next Article

Research article Special Issues

An improved signature model of multivariate polynomial public key cryptosystem against key recovery attack

Xin Wang ^1,2,
Bo Yang ^{1
,
,}

1.
School of Computer Science, Shaanxi Normal University, Xi’an, 710119, China
2.
School of Electronic Information and Artificial Intelligence, Shaanxi University of Science & Technology, Xi’an, 710021, China

Received: 16 June 2019 Accepted: 18 August 2019 Published: 23 August 2019

An improved signature model of multivariate polynomial public key cryptosystem to resist the key recovery attack is presented in this paper. Two pairs of public keys are added to design new authentication conditionals for public keys, and then the verification is not only to verify the original external information but also the exact internal kernel information. It requires both the corresponding private key and the exact internal node information to produce an accurate signature, so that a forged signature by key recovery attack cannot pass the verification without the exact private key. To illustrate this, the classic HFE (Hidden Fields Equations) scheme is taken as an example to clarify the signing and verifying process in detail. It provides a useful supplement to the research and designing of secure digital signature schemes in the quantum age.
- multivariate polynomial,
- public key cryptosystem,
- signature,
- key recovery attack
Citation: Xin Wang, Bo Yang. An improved signature model of multivariate polynomial public key cryptosystem against key recovery attack[J]. Mathematical Biosciences and Engineering, 2019, 16(6): 7734-7750. doi: 10.3934/mbe.2019388

Related Papers:

Abstract

An improved signature model of multivariate polynomial public key cryptosystem to resist the key recovery attack is presented in this paper. Two pairs of public keys are added to design new authentication conditionals for public keys, and then the verification is not only to verify the original external information but also the exact internal kernel information. It requires both the corresponding private key and the exact internal node information to produce an accurate signature, so that a forged signature by key recovery attack cannot pass the verification without the exact private key. To illustrate this, the classic HFE (Hidden Fields Equations) scheme is taken as an example to clarify the signing and verifying process in detail. It provides a useful supplement to the research and designing of secure digital signature schemes in the quantum age.

References

[1]	A. Huelsing, D. Butin, S. Gazdag, et al., XMSS: eXtended Merkle Signature Scheme, RFC 8391 (May 2018). Available from: https://tools.ietf.org/html/rfc8391.
[2]	R. E. Bansarkhani and R. Misoczki, G-Merkle: A hash-based group signature scheme from standard assumptions, PQCrypto, (2018), 441–463.
[3]	Y. Ashino and R. Sasaki, Proposal of digital forensic system using security device and hysteresis signature, IEEE Compt. Soc., 2 (2008), 3–7.
[4]	S. Tezuka, R. Uda and K. Okada, ADEC: Assured deletion and verifiable version control for cloud storage, AINA, 11 (2012), 23–30.
[5]	Shor and W. Peter, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SICOMP, 41 (1999), 1484–1509.
[6]	J. Ding and B. Yang, Multivariate public key cryptography, PQCrypto, (2008), 193–234.
[7]	M. Garay and D. Johnson, Computers and intractability: a guide to the theory of NP-Completeness, New York, USA, W.H. Freeman and Company, 1979.
[8]	A. Kipnis, J. Patarin and L. Goubin, Unbalanced oil and vinegar signature schemes, Eurocrypt, (1999), 206–222.
[9]	J. Ding and D. Schmidt, Rainbow, a new multivariable polynomial signature scheme, Appl. Cryptogr. Net. Secur., (2005), 164–175.
[10]	M. S. Chen, A. Hülsing, J. Rijneveld, et al., From 5-pass MQ-based identification to MQ-based signatures, International Conference On, Part II. Springer-Verlag New York, Inc., (2016), 135–165.
[11]	A. Petzoldt, A. Szepieniec and M. S. E. Mohamed, A practical multivariate blind signature scheme, International Conference on Financial Cryptography & Data Security. Springer, Cham, (2017), 437–454.
[12]	Y. Hashimoto, Key recovery attacks on multivariate public key cryptosystems derived from quadratic forms over an extension field, IEICE T. Fund. Electr., 100 (2017), 18–25.
[13]	C. Wolf and B. Preneel, Large superfluous keys in multivariate quadratic asymmetric systems, PKC, (2005), 275–287.
[14]	C. Wolf and B. Preneel, Equivalent keys in HFE, c* , and variations, Mycrypt, (2005), 33–49.
[15]	J. C. Faugère, D. Gligoroski, L. Perret, et al., A polynomial-time key-recovery attack on MQQ cryptosystems, IACR International Workshop on Public Key Cryptography. Springer, Berlin, Heidelberg, (2015), 150–174.
[16]	N. Courtois, A. Klimov, J. Patarin, et al., Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Proc. Eurocrypt, (2000), 392–407.
[17]	A. Biryukov, C. D. Christophe, B. An, et al., A toolbox for cryptanalysis: Linear and affine equivalence algorithms, Lect. Notes Comput. Sci., (2003), 33–50.
[18]	Y. H. Hu, L. C. Wang, C. Y. Chou, et al., Similar keys of multivariate quadratic public key cryptosystems, International Conference on Cryptology & Network Security. Springer-Verlag, (2005), 211–222.
[19]	C. Bouillaguet, P. A. Fouque, A. Joux, et al., A family of weak keys in HFE and the corresponding practical key-recovery, J. Math. Cryptol., 5 (2012), 247–275.
[20]	H. Wang, H. Zhang and S. Tang, Key recovery on several matrix public-key encryption schemes, IET Inform. Secur., 10 (2016), 152–155.
[21]	D. Cabarcas, D. Smith-Tone and J. A. Verbel, Key recovery attack for ZHFE, International Workshop on Post-quantum Cryptography. Springer, Cham, (2017), 289–308.
[22]	J. Porras, J. Baena and J. Ding, ZHFE, a new multivariate public key encryption scheme, International Workshop on Post-Quantum Cryptography, (2014), 229–245.
[23]	A. Petzoldt, M. S. Chen , J. Ding, et al., HMFEv-an efficient multivariate signature scheme, International Workshop on Post-Quantum Cryptography. Springer, Cham, (2017), 205–223.
[24]	L. Bettale, J. C. Faugère and L. Perret, Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic, Design. Code. Cryptogr., 69 (2013), 1–52.
[25]	J. Vates and D. Smith-Tone, Key recovery attack for all parameters of HFE-, PQCrypto, (2017), 272–288.
[26]	J. Patarin, Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms, Eurocrypt, (1996), 33–48.
[27]	A. Szepieniec, W. Beullens and B. Preneel, MQ signatures for PKI, PQCrypto, (2017), 224–240.
[28]	A. Szepieniec and B. Preneel, Block-anti-circulant unbalanced oil and vinegar, (2019). Available from: https://eprint.iacr.org/2019/046.pdf.
[29]	D. J. Bernstein, J. Buchmann and E. Dahmen, Introduction to post-quantum cryptography, Post-Quantum Cryptography, 1st ed. New York, USA: Springer, Heidelberg, 2010.
[30]	Y. Hashimoto, Multivariate public key cryptosystems, Math. Model.r Next-Gen. Cryptogr., 29 (2017), 17–42.
[31]	H. Gilbert, J. Plût, and J. Treger, Key-recovery attack on the ASASA cryptosystem with expanding S-boxes, Advances in Cryptology-CRYPTO 2015. Springer Berlin Heidelberg, (2015), 475–490.
[32]	E. Thomae, About the security of multivariate quadratic public key schemes, Ph.D thesis, Ruhr-University in Bochum, Germany, 2013.
[33]	A. Petzoldt, Selecting and reducing key sizes for multivariate cryptography, Ph.D thesis, Technische Universität Darmstadt in Germany, 2013.
[34]	C. Park, Cryptanalysis of matrix-based UOV, Finite Fields Th. App., 50 (2018), 209–221.
[35]	A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem by relinearization, Proc. Crypto, (1999), 19–30.
[36]	Y. Hashimoto, On the security of HMFEv, (2017). Available from: https://www.researchgate.net/publication/318543302_On_the_security_of_HMFEv.

Reader Comments

Your name:*

Email:*
© 2019 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)