Efficient Inversion of Rational Maps over Finite Fields

Efficient Inversion of Rational Maps over Finite Fields

Saturday, December 1, 2007
Antonio Cafure, Guillermo Matera and Ariel Waissbein
Institute for Mathematics and its Applications (IMA) Volume 146

We study the problem of finding the inverse image of a point in the image of a rational 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 public–key cryptographic scheme. Given an element y_0 in F(F_q^n), we are able to compute the set of values x_0 in F_q^n for which F(x_0) = y_0 holds with O(Tn^{4.38}D^{2.38} delta log_2 q) bit operations, up to logarithmic terms. Here T is the cost of the evaluation of F_1,..., F_n, D is the degree of F and delta is the degree of the graph of F.

Related information

Projects
Public-Key Cryptography Based on Polynomial Equations

Published In:

Institute for Mathematics and its Applications (IMA) Volume 146: Algorithms in Algebraic Geometry. Editors are Alicia Dickenstein, Frank-Olaf Schreyer, and Andrew J. Sommese.

Keywords

public-key cryptography, multivariate polynomial cryptography, finite fields, polynomial system solving, matrices of fixed displacement rank.