Efficient Algorithms for Solving Under-determined Multivariate Quadratic Polynomials(劣決定系の多変数二次多項式を解く効率的なアルゴリズム)

Chen Yilong

(指導教員:高木 剛 教授/数理情報第1研究室


Solving multivariate quadratic polynomials over finite fields occupies an important position in evaluating the security of multivariate cryptography. It could not only be used for solving public key systems directly, but also appears in the last step of algebraic attacks for recovering the secret keys. Recently the underdetermined case where the number of variables is greater than the number of equations attracted more interests because of the proposals of MAYO and QR-UOV. In this thesis, we proposed some efficient algorithms for solving underdetermined multivariate quadratic polynomials.

During these two years, I learned a lot about cryptography and other topics in mathematical informatics. I would like to express my heartfelt gratitude to my supervisor Professor Tsuyoshi Takagi and all members in the laboratory. Without their invaluable instructions, this study could not have been completed.