Inverting bijective polynomial maps over finite fields
Antonio Cafure, Guillermo Matera, Ariel Waissbein · 2006
We study the problem of inverting a bijective polynomial map F: Fqn→ Fqnover a finite field Fq. Our interest mainly stems from the case where F encodes a permutation given by some cryptographic scheme. Given y(0)∈ Fqn, we are able to compute the value x(0)∈ Fqnfor which F(x(0)) = y(0)holds in time O(LnO(1)δ4) up to logarithmic terms. Here L is the cost of the evaluation of F and δ is a geometric invariant associated to the graph of the polynomial map F, called its degree.