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
id todo:paper_14244003_v_n_p27_Cafure
record_format dspace
spelling todo:paper_14244003_v_n_p27_Cafure2023-10-03T16:13:34Z Inverting bijective polynomial maps over finite fields Cafure, A. Matera, G. Waissbein, A. Computational geometry Conformal mapping Cryptography Finite element method Graph theory Finite fields Permutation Polynomial maps Polynomials 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. Fil:Cafure, A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. CONF info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_14244003_v_n_p27_Cafure
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Computational geometry
Conformal mapping
Cryptography
Finite element method
Graph theory
Finite fields
Permutation
Polynomial maps
Polynomials
spellingShingle Computational geometry
Conformal mapping
Cryptography
Finite element method
Graph theory
Finite fields
Permutation
Polynomial maps
Polynomials
Cafure, A.
Matera, G.
Waissbein, A.
Inverting bijective polynomial maps over finite fields
topic_facet Computational geometry
Conformal mapping
Cryptography
Finite element method
Graph theory
Finite fields
Permutation
Polynomial maps
Polynomials
description 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.
format CONF
author Cafure, A.
Matera, G.
Waissbein, A.
author_facet Cafure, A.
Matera, G.
Waissbein, A.
author_sort Cafure, A.
title Inverting bijective polynomial maps over finite fields
title_short Inverting bijective polynomial maps over finite fields
title_full Inverting bijective polynomial maps over finite fields
title_fullStr Inverting bijective polynomial maps over finite fields
title_full_unstemmed Inverting bijective polynomial maps over finite fields
title_sort inverting bijective polynomial maps over finite fields
url http://hdl.handle.net/20.500.12110/paper_14244003_v_n_p27_Cafure
work_keys_str_mv AT cafurea invertingbijectivepolynomialmapsoverfinitefields
AT materag invertingbijectivepolynomialmapsoverfinitefields
AT waissbeina invertingbijectivepolynomialmapsoverfinitefields
_version_ 1782025650844991488

Ejemplares similares