- Title
- Efficient Inversion of Rational Maps over Finite Fields
- Authors
- Antonio Cafure, Guillermo Matera and Ariel Waissbein
- In
- Institute for Mathematics and its Applications (IMA) Volume 146: Algorithms in Algebraic Geometry. Editors are Alicia Dickenstein, Frank-Olaf Schreyer, and Andrew J. Sommese.
- Date published
- 2007-12
- Keywords
- public-key cryptography, multivariate polynomial cryptography, finite fields, polynomial system solving, matrices of fixed displacement rank.

## 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.