Abstract
Solving systems of m \(\mathcal M\)ultivariate \(\mathcal Q\)uadratic (\(\mathcal{MQ}\)) equations in n variables is one of the main challenges of algebraic cryptanalysis. Although the associated \(\mathcal{MQ}\)-problem is proven to be NP-complete, we know that it is solvable in polynomial time over fields of even characteristic if either m ≥ n(n − 1)/2 (overdetermined) or n ≥ m(m + 1) (underdetermined). It is widely believed that m = n has worst case complexity. Actually in the overdetermined case Gröbner Bases algorithms show a gradual decrease in complexity from m = n to m ≥ n(n − 1)/2 as more and more equations are available. For the underdetermined case no similar behavior was known. Up to now the best way to deal with the case m < n < m(m + 1) was to randomly guess variables until m = n. This article shows how to smartly use additional variables and thus obtain a gradual change of complexity over even characteristics also for the underdetermined case. Namely, we show how a linear change of variables can be used to reduce the overall complexity of solving a \(\mathcal{MQ}\)-system with m equations and n = ωm variables for some ω ∈ ℚ> 1 to the complexity of solving a \(\mathcal{MQ}\)-system with only \((m-\left\lfloor \omega\right\rfloor+1)\) equations and variables, respectively. Our algorithm can be seen as an extension of the previously known algorithm from Kipnis-Patarin-Goubin (extended version of Eurocrypt ’99) and improves an algorithm of Courtois et al. which eliminates \(\left\lfloor \mbox{log}_2\omega\right\rfloor\) variables. For small ω we also adapt our algorithm to fields of odd characteristic. We apply our result to break current instances of the Unbalanced Oil and Vinegar public key signature scheme that uses n = 3m and hence ω = 3.
Chapter PDF
Similar content being viewed by others
References
Bardet, M., Faugère, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In: Gianni, P. (ed.) MEGA 2005, Sardinia, Italy (2005)
Bettale, L., Faugère, J.-C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. Journal of Mathematical Cryptology 3, 177–197 (2009)
Braeken, A., Wolf, C., Preneel, B.: A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes. In: Menezes, A.J. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 29–43. Springer, Heidelberg (2005), http://eprint.iacr.org/2004/222/
Computational Algebra Group, University of Sydney. The MAGMA Computational Algebra System for Algebra, Number Theory and Geometry, http://magma.maths.usyd.edu.au/magma/
Courtois, N.T.: Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 182–199. Springer, Heidelberg (2003)
Courtois, N., Goubin, L., Meier, W., Tacier, J.-D.: Solving Underdefined Systems of Multivariate Quadratic Equations. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 211–227. Springer, Heidelberg (2002)
Courtois, N.T., Daum, M., Felke, P.: On the Security of HFE, HFEv- and Quartz. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 337–350. Springer, Heidelberg (2003), http://eprint.iacr.org/2002/138
Courtois, N.T., Klimov, A.B., Patarin, J., Shamir, A.: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000), Extended Version: http://www.minrank.org/xlfull.pdf
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F 4). Journal of Pure anNational Institute of Standards and Technologyd Applied Algebra 139, 61–88 (1999)
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5). In: International Symposium on Symbolic and Algebraic Computation — ISSAC 2002, pp. 75–83. ACM Press (July 2002)
Faugère, J.-C., Joux, A.: Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003)
Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic Cryptanalysis of McEliece Variants with Compact Keys. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 279–298. Springer, Heidelberg (2010)
Fischer, S., Meier, W.: Algebraic Immunity of S-Boxes and Augmented Functions. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 366–381. Springer, Heidelberg (2007)
Garey, M.R., Johnson, D.S.: Computers and Intractability — A Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979)
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced Oil and Vinegar signature schemes — extended version, 17 pages (June 11, 2003), http://www.citeseer/231623.html
Murphy, S., Robshaw, M.J.: Essential Algebraic Structure within the AES. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 1–16. Springer, Heidelberg (2002)
Patarin, J.: The oil and vinegar signature scheme. Presented at the Dagstuhl Workshop on Cryptography (September 1997), transparencies
Petzoldt, A., Thomae, E., Bulygin, S., Wolf, C.: Small Public Keys and Fast Verification for \(\mathcal{M}\)ultivariate \(\mathcal{Q}\)uadratic Public Key Systems. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 475–490. Springer, Heidelberg (2011)
Sugita, M., Kawazoe, M., Perret, L., Imai, H.: Algebraic Cryptanalysis of 58-Round SHA-1. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 349–365. Springer, Heidelberg (2007)
Wolf, C., Preneel, B.: Equivalent Keys in HFE, C*, and Variations. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 33–49. Springer, Heidelberg (2005); Extended version, http://eprint.iacr.org/2004/360/ , 15 pages
Wolf, C., Preneel, B.: Equivalent keys in multivariate quadratic public key systems. Journal of Mathematical Cryptology 4(4), 375–415 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 International Association for Cryptologic Research
About this paper
Cite this paper
Thomae, E., Wolf, C. (2012). Solving Underdetermined Systems of Multivariate Quadratic Equations Revisited. In: Fischlin, M., Buchmann, J., Manulis, M. (eds) Public Key Cryptography – PKC 2012. PKC 2012. Lecture Notes in Computer Science, vol 7293. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30057-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-30057-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30056-1
Online ISBN: 978-3-642-30057-8
eBook Packages: Computer ScienceComputer Science (R0)