Navegar

Colección

Datos Estadísticas

Conferencia

Estamos trabajando para incorporar este artículo al repositorio

Abstract:

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.

Registro:

Documento: Conferencia
Título:Inverting bijective polynomial maps over finite fields
Autor:Cafure, A.; Matera, G.; Waissbein, A.
Ciudad:Punta del Este
Filiación:Depto. de Matemática, FCEyN, Pabellón I, (C1428EHA) Buenos Aires, Argentina
Instituto del Desarrollo Humano, Universidad Nac. Gral. Sarmiento, J. M. Gutiérrez 1150, (1613) Los Polvorines, Argentina
CONICET, Argentina
CoreLabs., CORE ST, (C1414CTU) Cdad. de Bs. As, Argentina
ITBA, Av. Eduardo Madero 399, (C1106ACD) Cdad. de Buenos Aires, Argentina
Palabras clave:Computational geometry; Conformal mapping; Cryptography; Finite element method; Graph theory; Finite fields; Permutation; Polynomial maps; Polynomials
Año:2006
Página de inicio:27
Página de fin:31
Título revista:2006 IEEE Information Theory Workshop, ITW 2006
Título revista abreviado:2006 IEEE Inform. Theory Workshop
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14244003_v_n_p27_Cafure

Referencias:

  • Shparlinski, I., (1992) Computational and Algorithmic Problems in Finite Fields, , Dordrecht Boston London: Kluwcr Academic Publishers
  • Huang, M.-D., Wong, Y.-C., Solvability of systems of polynomial congruences modulo a large prime (1999) Comput. Complexity, 8 (3), pp. 227-257
  • Bardet, M., Faugère, J.-C., Salvy, B., (2003) Complexity of Gröbner Basis Computation for Semi-regular Overdetermined Sequences over double-struck F sign2 with Solutions in double-struck F sign2, , http://www.inria.fr/rrrt/rr-5049.html, Rapport de Recherche INRIA RR-5049
  • Cafure, A., Matera, G., Fast computation of a rational point of a variety over a finite field (2005) Math. Comput., , www.arxiv.org/pdf/math.AG/0406085, To appear
  • Garey, M., Johnson, D., (1979) Computers and Intractability: A Guide to the Theory of NP-completeness, , San Francisco: Freeman
  • Von Zur Gathen, J., Karpinski, M., Shparlinski, I., Counting curves and their projections (1997) Comput. Complexity, 6, pp. 64-99
  • Cafure, A., Matera, G., Improved explicit estimates on the number of solutions of equations over a finite field (2005) Finite Fields Appl., , www.arxiv.org/pdf/math.NT/0405302, To appear
  • Sturtivant, C., Zhang, Z.-L., Efficiently inverting bijections given by straight line programs (1990) Proc. FOCS'90, pp. 327-334. , IEEE
  • Kipnis, A., Shamir, A., Cryptanalysis of the HFE Public Key Cryptosystem by relinearization (1999) Proceedings CRYPTO'99, 1666, pp. 19-30. , ser. Lecture Notes in Comput. Sci., Berlin: Springer
  • Courtois, N., Klimov, A., Patarin, J., Shamir, A., Efficient algorithms for solving overdefined systems of multivariate polynomial equations (2000) EUROCRYPT 2000, 1807, pp. 71-79. , ser. Lecture Notes in Comput. Sci., B. Preneel, Ed., Berlin: Springer
  • Matsumoto, T., Imai, H., A class of asymmetric crypto-systems based on polynomials over finite rings (1983) IEEE Intern. Symp. Inform. Theory, Abstracts of Papers, pp. 131-132
  • Wolf, C., Preneel, B., Taxonomy of public key schemes based on the problem of multivariate quadratic equations (2005) Cryptology EPrint Archive, Report, 2005 (77). , http://eprint.iacr.org/
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24 (3), pp. 239-277
  • Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L., The hardness of polynomial equation solving (2003) Found, Comput, Math., 3 (4), pp. 347-420
  • Giusti, M., Hägele, K., Heintz, J., Morais, J., Montaña, J., Pardo, L., Lower bounds for Diophantine approximation (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317
  • Pardo, L., Martín, J.S., Deformation techniques to solve generalized Pham systems (2004) Theoret, Comput, Sci., 315, pp. 593-625
  • Kaltofen, E., Effective Noether irreducibility forms and applications (1995) J. Comput. System Sci., 50 (2), pp. 274-295
  • Lidl, R., Niederreiter, H., (1983) Finite Fields, , Addison-Wesley
  • Von Zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge: Cambridge Univ. Press
  • Bini, D., Pan, V., (1994) Polynomial and Matrix Computations, , ser. Progress in Theoretical Computer Science. Boston: Birkhäuser
  • Baur, W., Strassen, V., The complexity of partial derivatives (1983) Theoret. Comput. Sci., 22, pp. 317-330
  • Pan, V., (2001) Structured Matrices and Polynomials. Unified Superfast Algorithms, , Boston: Birkhäuser
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17, pp. 154-211

Citas:

---------- APA ----------
Cafure, A., Matera, G. & Waissbein, A. (2006) . Inverting bijective polynomial maps over finite fields. 2006 IEEE Information Theory Workshop, ITW 2006, 27-31.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14244003_v_n_p27_Cafure [ ]
---------- CHICAGO ----------
Cafure, A., Matera, G., Waissbein, A. "Inverting bijective polynomial maps over finite fields" . 2006 IEEE Information Theory Workshop, ITW 2006 (2006) : 27-31.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14244003_v_n_p27_Cafure [ ]
---------- MLA ----------
Cafure, A., Matera, G., Waissbein, A. "Inverting bijective polynomial maps over finite fields" . 2006 IEEE Information Theory Workshop, ITW 2006, 2006, pp. 27-31.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14244003_v_n_p27_Cafure [ ]
---------- VANCOUVER ----------
Cafure, A., Matera, G., Waissbein, A. Inverting bijective polynomial maps over finite fields. 2006 IEEE Inform. Theory Workshop. 2006:27-31.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14244003_v_n_p27_Cafure [ ]