Inverting bijective polynomial maps over finite fields

We study the problem of inverting a bijective polynomial map F: double-struck F signq n → double-struck F sign q n over a finite field double-struck F signq. Our interest mainly stems from the case where F encodes a permutation given by some cryptographic scheme. Given y(0) ∈ double-struck F signq n...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Cafure, A., Matera, G., Waissbein, A.
Formato: CONF
Materias:
Computational geometry
Conformal mapping
Cryptography
Finite element method
Graph theory
Finite fields
Permutation
Polynomial maps
Polynomials
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_14244003_v_n_p27_Cafure
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
Descripción
Sumario:We study the problem of inverting a bijective polynomial map F: double-struck F signq n → double-struck F sign q n over a finite field double-struck F signq. Our interest mainly stems from the case where F encodes a permutation given by some cryptographic scheme. Given y(0) ∈ double-struck F signq n, we are able to compute the value x(0) ∈ double-struck F signq n for 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. © 2006 IEEE.

Ejemplares similares