Title
Inverting bijective polynomial maps over finite fields
Authors
Antonio Cafure, Guillermo Matera and Ariel Waissbein
In
2006 IEEE Information Theory Workshop (ITW 2006), Monday, March 13, through Friday, March 17, 2006. Punta del Este, Uruguay.
Date published
2006-03
Keywords
public-key cryptography, polynomial equation solving.

Abstract

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.

Attachments