Degree of regularity of systems arising from a Weil descent

Polynomials systems arising from a Weil descent have many applications in cryptography, including to the HFE cryptosystem and to the elliptic curve discrete logarithm problem over small characteristic fields. Understanding the exact complexity of solving these systems is essential for the applications. A first step in that direction is to study the first fall degree of the systems. In this paper, we provide a rigorous general bound on the first fall degree of polynomial systems arising from a Weil descent. We then deduce heuristic complexity bounds for the resolution of these systems, and we support our heuristic analysis with experimental data.