Inverting bijective polynomial maps over finite fields

Inverting bijective polynomial maps over finite fields

Wednesday, March 1, 2006
Antonio Cafure, Guillermo Matera and Ariel Waissbein
2006 IEEE Information Theory Workshop, Punta del Este, Uruguay

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.

Related information

Projects
Public-Key Cryptography Based on Polynomial Equations