Institute for Mathematics and its Applications (IMA) Volume 146: Algorithms in Algebraic Geometry. Editors are Alicia Dickenstein, Frank-Olaf Schreyer, and Andrew J. Sommese.
Abstract
We study the problem of finding the inverse image of a point in the image of a rational map F: F_q^n -> F_q^n over a finite field F_q. Our interest mainly stems from the case where F encodes a permutation given by some public–key cryptographic scheme. Given an element y_0 in F(F_q^n), we are able to compute the set of values x_0 in F_q^n for which F(x_0) = y_0 holds with O(Tn^{4.38}D^{2.38} delta log_2 q) bit operations, up to logarithmic terms. Here T is the cost of the evaluation of F_1,..., F_n, D is the degree of F and delta is the degree of the graph of F.