- Inverting bijective polynomial maps over finite fields
- Antonio Cafure, Guillermo Matera and Ariel Waissbein
- 2006 IEEE Information Theory Workshop (ITW 2006), Monday, March 13, through Friday, March 17, 2006. Punta del Este, Uruguay.
- Date published
- public-key cryptography, polynomial equation solving.
We study the problem of inverting a bijective polynomial 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 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(Ln^O(1)D^4) up to logarithmic terms. Here L is the cost of
the evaluation of F and D is a geometric invariant associated to the graph of the polynomial map F, called its degree.