ACE Seminar: The last fall degree and an application to HFE

Speaker: Michiel Kosters

Date/Time: 01-Jan-1970, 00:00 UTC




We first briefly discuss the standard method for solving polynomial systems, using Groebner bases. Then we will discuss the first fall degree conjecture, which predicts the complexity of such computations. We present some evidence in favor and some evidence against this conjecture. We will propose a new concept, the last fall degree, which can be used to give complexity of Groebner basis computations as well, without any heuristics. Finally, we discuss how one can prove that HFE (hidden field equations) is insecure by bounding the complexity of Groebner basis algorithms using the last fall degree. 

This page was last modified on 27 Mar 2014.