Title :
Inverting bijective polynomial maps over finite fields
Author :
Cafure, Antonio ; Matera, Guillermo ; Waissbein, Ariel
Author_Institution :
Depto. de Matemática, FCEyN, UBA, Ciudad Universitaria, Pabellón I, (C1428EHA) Buenos Aires, Argentina. Instituto del Desarrollo Humano, Universidad Nac. Gral. Sarmiento, J. M. Gutiérrez 1150 1613) Los Polvorines, Argentina
Abstract :
We study the problem of inverting a bijective polynomial map F: Fqn→ Fqnover a finite field Fq. Our interest mainly stems from the case where F encodes a permutation given by some cryptographic scheme. Given y(0)∈ Fqn, we are able to compute the value x(0)∈ Fqnfor which F(x(0)) = y(0)holds in time O(LnO(1)δ4) up to logarithmic terms. Here L is the cost of the evaluation of F and δ is a geometric invariant associated to the graph of the polynomial map F, called its degree.
Keywords :
Application software; Arithmetic; Computational geometry; Costs; Equations; Galois fields; Performance evaluation; Polynomials; Public key; Public key cryptography;
Conference_Titel :
Information Theory Workshop, 2006. ITW '06 Punta del Este. IEEE
Conference_Location :
Punta del Este, Uruguay
Print_ISBN :
1-4244-0035-X
Electronic_ISBN :
1-4244-0036-8
DOI :
10.1109/ITW.2006.1633775