Degree of regularity of systems arising from a Weil descent

Hodges, Timothy;Petit, Christophe;Schlather, Jacob
(2012) Yet Another Conference on Cryptography (YACC 2012) — Location: Porquerolles Island (24.September.2012)

Files

16présentationoraleetrapporttechnique.pdf
  • Restricted Access
  • Adobe PDF
  • 242.82 KB
Request a copy

Details

Authors
  • Hodges, TimothyUniversity of Cincinatti
    Author
  • Petit, ChristopheUCLouvain
    Author
  • Schlather, JacobUniversity of Cincinatti
    Author
Abstract
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Hodges, T., Petit, C., & Schlather, J. (2012). Degree of regularity of systems arising from a Weil descent. Yet Another Conference on Cryptography (YACC 2012), Porquerolles Island. https://hdl.handle.net/2078.5/219389