Abstract
A Gröbner basis algorithm computes a good basis for an ideal of a polynomial ring and appears in various situations of cryptography. In particular, it has been used in the security analysis of multivariate public key cryptography (MPKC), and has been studied for a long time; however, it is far from a complete understanding. We consider the algebraic attack using a Gröbner basis algorithm for a new multivariate encryption scheme proposed by Jiahui Chen et al. at Theoretical Computer Science 2020. Their idea to construct a new scheme was to use the minus and plus modifiers to prevent known attacks, such as linearization attacks. Moreover, they discussed having a resistance to the algebraic attack using a Gröbner basis algorithm. However, in our experiments, the algebraic attack breaks their claimed 80- and 128-bit security parameters in reasonable times. It is necessary to understand whether their scheme can avoid such an attack by introducing a slight modification. In this paper, we theoretically describe why the algebraic attack breaks their scheme and give a precise complexity of the algebraic attack. As a result, we demonstrate that the algebraic attack can break the claimed 80- and 128-bit security parameters in the complexities of approximately 25 and 32 bits, respectively. Moreover, based on our complexity estimation of the algebraic attack, we conclude that the Chen et al. scheme is not practical.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bardet B, Faugère JC, Salvy B, Yang BY (2005) Asymptotic behavior of the index of regularity of quadratic semi-regular polynomial systems. In: 8th international symposium on effective methods in algebraic geometry (MEGA), pp 1–14
Bernstein DJ, Buchmann J, Dahmen E (eds) Post-quantum cryptography. Springer
Bettale L, Faugère JC, Perret L (2013) Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. Des Codes Cryptogr 69:1–52
Beullens W, Preneel B, Szepieniec A, Vercauteren F (2020) LUOV, Technical report, National Institute of Standards and Technology, Post-quantum cryptography, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-2-submissions Accessed 2020-5-10
Bosma W, Cannon J, Playoust C (1997) The Magma algebra system. I. The user language. J. Symbolic Comput 24:235–265
Casanova A, Faugére JC, Macario-Rat G, Patarin J, Perret L, Ryckeghem J (2020) GeMSS, Technical report, National Institute of Standards and Technology, Post-quantum cryptography. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-2-submissions. Accessed 2020-5-10
Chen J, Ling J, Ning J, Lau TSC, Wang Y (2020) A new encryption scheme for multivariate quadratic systems. Theor Comput Sci 809:372–383
Cartor R, Smith-Tone D (2018) EFLASH: a new multivariate encryption scheme. In: SAC 2018, LNCS, vol 11349. Springer, pp 281–299
Ding J, Gower JE Schmidt DS (2006) Multivariate public key cryptosystems. Springer
Ding J, Schmidt DS (2005) Rainbow, a new multivariate polynomial signature scheme. In: ACNS 2005, LNCS, vol 3531. Springer, pp 164–175
Ding J, Chen MS, Petzoldt A, Schmidt DS, Yang BY (2020) Rainbow, Technical report, National Institute of Standards and Technology, Post-quantum cryptography. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-2-submissions. Accessed 2020-5-10
Faugère JC (1999) A new efficient algorithm for computing Gröbner bases (F4). J Pure Appl Algebra 139:61–88
Faugère JC (2002) A new efficient algorithm for computing Gröbner Bases without reduction to zero (F5). ISSAC 2002:75–83
Faugère JC, Joux A (2003) Algebraic cryptanalysis of hidden field equations (HFE) using Groöbner bases. In: Crypto 2003, LNCS, vol 2729. Springer, pp 44–60
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H Freeman, Company
Ikematsu Y, Perlner R, Smith-Tone D, Takagi T, Vates J (2018) HFERP - a new multivariate encryption scheme. In: PQCrypto 2018, LNCS, vol 10786. Springer, pp 396–416
Kipnis A, Patarin L, Goubin L (1999) Unbalanced oil and vinegar schemes. In: EUROCRYPT 1999, LNCS, vol 1592. Springer, pp 206–222
Matsumoto T, Imai H (1988) Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: EUROCRYPT 1988, LNCS, vol 330. Springer, pp 419–453
National Institute of Standards and Technology (2020) Post-quantum cryptography, Round 2 submission. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-2-Submissions. Accessed 2020-5-10
Patarin J (1995) Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt 88. In:CRYPTO 1995, LNCS, vol 963, Springer, pp 248–261
Patarin J (1996) Hidden field equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: EUROCRYPT, LNCS, vol 1070. Springer, pp 33–48 (1996)
Patarin J, Courtois NT, Goubin L (2001) QUARTZ, 128-bit long digital signatures. In: CT-RSA 2001, LNCS, vol 2020. Springer, pp 282–297
Petzoldt A, Chen MS, Yang BY, Tao C, Ding J (2015) Design principles for HFEv- based signature schemes. In: ASIACRYPT 2015, LNCS, vol 9452. Springer, pp 311–334
Szepieniec A, Ding J, Preneel B (2016) Extension field cancellation: a new central trapdoor for multivariate quadratic systems. In: PQCrypto 2016, LNCS, vol 9606. Springer, pp 182–196
Tao C, Diene A, Tang S, Ding J (2013) Simple matrix scheme for encryption. In: PQCrypto 2013, LNCS, vol 7932. Springer, pp 231–242
Yang B-Y, Chen J-M (2004) All in the XL family: theory and practice. In: ICISC 2004, LNCS, vol 3506. Springer, pp 67–86
Acknowledgements
This work was supported by JST CREST Grant Number JPMJCR14D6, JSPS KAKENHI Grant Number JP19K20266, JP20K19802 and 2019 IMI Joint Use Research Program Short-term Joint Research “New Development of Constructing Next-Generation Cryptography via Unified Approaches of Mathematics Theory, Computation and Cryptology”.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Ikematsu, Y., Nakamura, S. (2022). Security Analysis via Algebraic Attack Against “A New Encryption Scheme for Multivariate Quadratic System”. In: Giri, D., Raymond Choo, KK., Ponnusamy, S., Meng, W., Akleylek, S., Prasad Maity, S. (eds) Proceedings of the Seventh International Conference on Mathematics and Computing . Advances in Intelligent Systems and Computing, vol 1412. Springer, Singapore. https://doi.org/10.1007/978-981-16-6890-6_2
Download citation
DOI: https://doi.org/10.1007/978-981-16-6890-6_2
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-16-6889-0
Online ISBN: 978-981-16-6890-6
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)