SHARE
Inverting bijective polynomial maps over finite fields.
We study the problem of inverting a bijective polynomial map F:(F_q)^n -> (F_q)^n over a inite field F_q. Our interest mainly stems from the case where F encodes a permutation given by some cryptographic scheme. Given y_0 in (F_q)^n we are able to compute the value x_0 in (F_q)^n for which F(x_0) = y_0 holds in time O(LnO(1)\delta^4) up to logarithmic terms. Here L is the cost of the evaluation of F and \delta is a geometric invariant associated to the graph of the polynomial map F, called its degree.