Research article Special Issues

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

  • 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.

    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:

  • 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.


    加载中


    [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
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3191) PDF downloads(463) Cited by(3)

Article outline

Figures and Tables

Figures(4)  /  Tables(3)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog