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, Antonio Artemio, Matera, Guillermo
Publicado: 2006
Materias:
Computational geometry
Conformal mapping
Cryptography
Finite element method
Graph theory
Finite fields
Permutation
Polynomial maps
Polynomials
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14244003_v_n_p27_Cafure
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 paper:paper_14244003_v_n_p27_Cafure
record_format dspace
spelling paper:paper_14244003_v_n_p27_Cafure2023-06-08T16:13:50Z Inverting bijective polynomial maps over finite fields Cafure, Antonio Artemio Matera, Guillermo 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. 2006 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14244003_v_n_p27_Cafure 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, Antonio Artemio
Matera, Guillermo
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.
author Cafure, Antonio Artemio
Matera, Guillermo
author_facet Cafure, Antonio Artemio
Matera, Guillermo
author_sort Cafure, Antonio Artemio
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
publishDate 2006
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14244003_v_n_p27_Cafure
http://hdl.handle.net/20.500.12110/paper_14244003_v_n_p27_Cafure
work_keys_str_mv AT cafureantonioartemio invertingbijectivepolynomialmapsoverfinitefields
AT materaguillermo invertingbijectivepolynomialmapsoverfinitefields
_version_ 1768544791713284096

Ejemplares similares