日時：　平成27年1月15日 10時00分-12時00分

場所：　情報科学研究科 5階コラボレーションルーム7

講演者氏名： Chen-Mou Cheng
国立台湾大学准教授

講演題目： 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.

[戻る]