Summary: Following up a series of works by Kipnis-Patarin-Goubin [A. Kipnis et al., Eurocrypt 1999, Lect. Notes Comput. Sci. 1592, 206–222 (1999; Zbl 0933.94031)], Courtois-Goubin-Meier-Tacier [N. Courtois et al., PKC 2001, Lect. Notes Comput. Sci. 2274, 211–227 (2002; Zbl 1055.94534)], and Thomae-Wolf [E. Thomae and C. Wolf, PKC 2012, Lect. Notes Comput. Sci. 7293, 156–171 (2012; Zbl 1290.94134)], in PQCrypto 2013 H. Miura, Y. Hashimoto and T. Takagi [Lect. Notes Comput. Sci. 7932, 118–135 (2013; Zbl 1306.94076)] proposed an efficient algorithm for solving a class of underdetermined multivariate quadratic equations. Their algorithm does not use any generic Gröbner-basis solving techniques and asymptotically requires the least degree of underdeterminedness among all similar algorithms in the current literature. Building on top of their work, in this paper we focus on solving polynomially underdetermined multivariate quadratic equations over fields of odd characteristics. We show that we can further improve the applicable range of the Miura-Hashimoto-Takagi algorithm essentially for free. Furthermore, we show how to allow a certain degree of trade-off between applicable range and running time. Last but not least, we show that the running time of the improved algorithm is actually polynomial in number of equations and variables. To the best of our knowledge, this is the first result showing that this class of polynomially underdetermined multivariate quadratic equations over fields of odd characteristics can be solved in polynomial time.
For the entire collection see [Zbl 1296.94005].