---

Date: 2015/1/15

Place: Collaboration Room #7 10:00 - 12:00

Name: Chen-Mou Cheng
    Associate Professor, National Taiwan University


Title: A polynomial-time algorithm for solving underdetermined multivariate quadratic equations

Following up a series of works by Kipnis-Patarin-Goubin, Courtois-Goubin-Meier-Tacier, and Thomae-Wolf, in PQCrypto 2013 Miura, Hashimoto, and Takagi proposed an efficient algorithm for solving a class of underdetermined multivariate quadratic equations. Their algorithm does not use any generic Groebner-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 talk I will focus on solving polynomially underdetermined multivariate quadratic equations over a finite field. I will show that we can further improve the applicable range of the Miura-Hashimoto-Takagi algorithm essentially for free. Furthermore, I will show how to allow a certain degree of trade-off between applicable range and running time. Last but not least, I will 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 a finite field can be solved in polynomial time.

---

---

[back]