×

Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem. (English) Zbl 1092.94024

Summary: Recently, the first author introduced some cryptographic functions closely related to the Diffie-Hellman problem called \(P\)-Diffie-Hellman functions. We show that the existence of a low-degree polynomial representing a \(P\)-Diffie-Hellman function on a large set would lead to an efficient algorithm for solving the Diffie-Hellman problem. Motivated by this result we prove lower bounds on the degree of such interpolation polynomials. Analogously, we introduce a class of functions related to the discrete logarithm and show similar reduction and interpolation results.

MSC:

94A60 Cryptography
11T06 Polynomials over finite fields
11A07 Congruences; primitive roots; residue systems

Keywords:

lower bounds
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Bach, J.O. Shallit, Algorithmic Number Theory, vol. 1: Efficient Algorithms, MIT Press, Cambridge, 1996.; E. Bach, J.O. Shallit, Algorithmic Number Theory, vol. 1: Efficient Algorithms, MIT Press, Cambridge, 1996. · Zbl 0873.11070
[2] Coppersmith, D.; Shparlinski, I., On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping, J. Cryptol., 13, 339-360 (2000) · Zbl 1038.94007
[3] El Mahassni, E.; Shparlinski, I., Polynomial representations of the Diffie-Hellman mapping, Bull. Austral. Math. Soc., 63, 467-473 (2001) · Zbl 0974.11040
[4] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (1999), Cambridge University Press: Cambridge University Press New York · Zbl 0936.11069
[5] E. Kiltz, A tool box of cryptographic functions related to the Diffie-Hellman function, Indocrypt’01, Lecture Notes in Computer Science, vol. 2247, Springer, Berlin, 2001, pp. 339-349.; E. Kiltz, A tool box of cryptographic functions related to the Diffie-Hellman function, Indocrypt’01, Lecture Notes in Computer Science, vol. 2247, Springer, Berlin, 2001, pp. 339-349. · Zbl 1011.94542
[6] Kiltz, E.; Winterhof, A., Lower bounds on weight and degree of bivariate polynomials related to the Diffie-Hellman mapping, Bull. AusMS, 69, 305-315 (2004) · Zbl 1070.11055
[7] T. Lange, A. Winterhof, Polynomial interpolation of the elliptic curve and XTR discrete logarithm, Proceedings of COCOON’02, Lecture Notes in Computer Science, vol. 2397, Springer, Berlin 2002, pp. 137-143.; T. Lange, A. Winterhof, Polynomial interpolation of the elliptic curve and XTR discrete logarithm, Proceedings of COCOON’02, Lecture Notes in Computer Science, vol. 2397, Springer, Berlin 2002, pp. 137-143. · Zbl 1077.94518
[8] T. Lange, A. Winterhof, Interpolation of the elliptic-curve Diffie-Hellman mapping, Proceedings of AAECC 15, Lecture Notes in Computer Science, vol. 2643, Springer, Berlin 2003, pp. 51-60.; T. Lange, A. Winterhof, Interpolation of the elliptic-curve Diffie-Hellman mapping, Proceedings of AAECC 15, Lecture Notes in Computer Science, vol. 2643, Springer, Berlin 2003, pp. 51-60. · Zbl 1030.11071
[9] Meidl, W.; Winterhof, A., A polynomial representation of the Diffie-Hellman mapping, Appl. Algebra Eng. Comm. Comput., 3, 313-318 (2002) · Zbl 1013.94012
[10] Meidl, W.; Winterhof, A., On the linear complexity profile of explicit nonlinear pseudorandom numbers, Inform. Proc. Lett., 85, 13-18 (2003) · Zbl 1042.68053
[11] Meletiou, G. C., Explicit form for the discrete logarithm over the field \(\operatorname{GF}(p, k)\), Arch. Math. (Brno), 29, 25-28 (1993) · Zbl 0818.11049
[12] Meletiou, G.; Mullen, G. L., A note on discrete logarithms in finite fields, Appl. Algebra Eng. Comm. Comput., 3, 75-78 (1992) · Zbl 0749.11055
[13] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A., Handbook of Applied Cryptography (1997), CRC Press: CRC Press Boca Raton, FL · Zbl 0868.94001
[14] Mullen, G. L.; White, D., A polynomial representation for logarithms in \(\operatorname{GF}(q)\), Acta Arith., 47, 255-261 (1986) · Zbl 0562.12018
[15] Niederreiter, H., A short proof for explicit formulas for discrete logarithms in finite fields, Appl. Algebra Eng. Comm. Comput., 1, 55-57 (1990) · Zbl 0726.11079
[16] Niederreiter, H.; Winterhof, A., Incomplete character sums and polynomial interpolation of the discrete logarithm, Finite Fields Appl., 8, 184-192 (2002) · Zbl 1017.11065
[17] D. Shanks, Class number, a theory of factorization and genera, in: Proceedings of the Symposium on Pure Mathematics, vol. 20, American Mathematical Society, Providence, RI, 1971, pp. 415-440.; D. Shanks, Class number, a theory of factorization and genera, in: Proceedings of the Symposium on Pure Mathematics, vol. 20, American Mathematical Society, Providence, RI, 1971, pp. 415-440. · Zbl 0223.12006
[18] I.E. Shparlinski, Number theoretic methods in cryptography. Complexity lower bounds, Progress in Computer Science and Applied Logic, vol. 17. Birkhäuser Verlag, Basel, 1999.; I.E. Shparlinski, Number theoretic methods in cryptography. Complexity lower bounds, Progress in Computer Science and Applied Logic, vol. 17. Birkhäuser Verlag, Basel, 1999. · Zbl 0912.11057
[19] Shparlinski, I. E., Cryptographic Applications of Analytic Number Theory (2003), Birkhäuser: Birkhäuser Basel · Zbl 1049.11010
[20] Wells, A. L., A polynomial form for logarithms modulo a prime, IEEE Trans. Inform. Theory, 30, 845-846 (1984) · Zbl 0558.12009
[21] Winterhof, A., A note on the interpolation of the Diffie-Hellman mapping, Bull. Austral. Math. Soc., 64, 475-477 (2001) · Zbl 0997.11108
[22] Winterhof, A., Polynomial interpolation of the discrete logarithm, Des. Codes Cryptogr., 25, 63-72 (2002) · Zbl 1008.94015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.