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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , |
| Formato: | Acta de conferencia Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2006
|
| Acceso en línea: | Registro en Scopus Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 06651caa a22007337a 4500 | ||
|---|---|---|---|
| 001 | PAPER-6879 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203635.0 | ||
| 008 | 190411s2006 xx ||||fo|||| 10| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-33751041255 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Cafure, A. | |
| 245 | 1 | 0 | |a Inverting bijective polynomial maps over finite fields |
| 260 | |c 2006 | ||
| 270 | 1 | 0 | |m Cafure, A.; Depto. de Matemática, FCEyN, Pabellón I, (C1428EHA) Buenos Aires, Argentina |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Shparlinski, I., (1992) Computational and Algorithmic Problems in Finite Fields, , Dordrecht Boston London: Kluwcr Academic Publishers | ||
| 504 | |a Huang, M.-D., Wong, Y.-C., Solvability of systems of polynomial congruences modulo a large prime (1999) Comput. Complexity, 8 (3), pp. 227-257 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Garey, M., Johnson, D., (1979) Computers and Intractability: A Guide to the Theory of NP-completeness, , San Francisco: Freeman | ||
| 504 | |a Von Zur Gathen, J., Karpinski, M., Shparlinski, I., Counting curves and their projections (1997) Comput. Complexity, 6, pp. 64-99 | ||
| 504 | |a 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 | ||
| 504 | |a Sturtivant, C., Zhang, Z.-L., Efficiently inverting bijections given by straight line programs (1990) Proc. FOCS'90, pp. 327-334. , IEEE | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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/ | ||
| 504 | |a Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24 (3), pp. 239-277 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Pardo, L., Martín, J.S., Deformation techniques to solve generalized Pham systems (2004) Theoret, Comput, Sci., 315, pp. 593-625 | ||
| 504 | |a Kaltofen, E., Effective Noether irreducibility forms and applications (1995) J. Comput. System Sci., 50 (2), pp. 274-295 | ||
| 504 | |a Lidl, R., Niederreiter, H., (1983) Finite Fields, , Addison-Wesley | ||
| 504 | |a Von Zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge: Cambridge Univ. Press | ||
| 504 | |a Bini, D., Pan, V., (1994) Polynomial and Matrix Computations, , ser. Progress in Theoretical Computer Science. Boston: Birkhäuser | ||
| 504 | |a Baur, W., Strassen, V., The complexity of partial derivatives (1983) Theoret. Comput. Sci., 22, pp. 317-330 | ||
| 504 | |a Pan, V., (2001) Structured Matrices and Polynomials. Unified Superfast Algorithms, , Boston: Birkhäuser | ||
| 504 | |a Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17, pp. 154-211 | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Depto. de Matemática, FCEyN, Pabellón I, (C1428EHA) Buenos Aires, Argentina | ||
| 593 | |a Instituto del Desarrollo Humano, Universidad Nac. Gral. Sarmiento, J. M. Gutiérrez 1150, (1613) Los Polvorines, Argentina | ||
| 593 | |a CONICET, Argentina | ||
| 593 | |a CoreLabs., CORE ST, (C1414CTU) Cdad. de Bs. As, Argentina | ||
| 593 | |a ITBA, Av. Eduardo Madero 399, (C1106ACD) Cdad. de Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a COMPUTATIONAL GEOMETRY |
| 690 | 1 | 0 | |a CONFORMAL MAPPING |
| 690 | 1 | 0 | |a CRYPTOGRAPHY |
| 690 | 1 | 0 | |a FINITE ELEMENT METHOD |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 690 | 1 | 0 | |a FINITE FIELDS |
| 690 | 1 | 0 | |a PERMUTATION |
| 690 | 1 | 0 | |a POLYNOMIAL MAPS |
| 690 | 1 | 0 | |a POLYNOMIALS |
| 700 | 1 | |a Matera, G. | |
| 700 | 1 | |a Waissbein, A. | |
| 711 | 2 | |c Punta del Este |d 13 March 2006 through 17 March 2006 |g Código de la conferencia: 68567 | |
| 773 | 0 | |d 2006 |h pp. 27-31 |p 2006 IEEE Inform. Theory Workshop |n 2006 IEEE Information Theory Workshop, ITW 2006 |z 142440035X |z 9781424400355 |t 2006 IEEE Information Theory Workshop, ITW 2006 | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-33751041255&partnerID=40&md5=d883ca2d16a347033a46cc4615bded6a |y Registro en Scopus |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_14244003_v_n_p27_Cafure |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14244003_v_n_p27_Cafure |y Registro en la Biblioteca Digital |
| 961 | |a paper_14244003_v_n_p27_Cafure |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/conferenceObject |a info:ar-repo/semantics/documento de conferencia |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 67832 | ||