nach oben

Designs, Codes and Cryptography

Erschienen in:

02.05.2018

Polynomial interpolation of the generalized Diffie–Hellman and Naor–Reingold functions

verfasst von: Thierry Mefenza, Damien Vergnaud

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1/2019

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In cryptography, for breaking the security of the Generalized Diffie–Hellman and Naor–Reingold functions, it would be sufficient to have polynomials with small weight and degree which interpolate these functions. We prove lower bounds on the degree and weight of polynomials interpolating these functions for many keys in several fixed points over a finite field.

Vorheriger Artikel Phased unitary Golay pairs, Butson Hadamard matrices and a conjecture of Ito’s

Nächster Artikel How many weights can a linear code have?

Actually, the security of Joux’s key exchange relies on the stronger decision bilinear Diffie–Hellman assumption in groups equipped with a bilinear map. This assumption implies the tripartite decision Diffie–Hellman assumption in the so-called target group of the bilinear map.

Diffie W., Hellman M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976).MathSciNetCrossRefMATH

Boneh, D.: The decision Diffie–Hellman problem. In: Buhler, J. (ed.) Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon, USA, June 21–25, 1998. Lecture Notes in Computer Science, Vol. 1423, pp. 48–63. Springer (1998).

Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th Annual Symposium on Foundations of Computer Science, pp. 458–467. IEEE Computer Society Press, Miami Beach, Florida (1997).

Naor M., Reingold O.: Number-theoretic constructions of efficient pseudo-random functions. J. ACM 51(2), 231–262 (2004).MathSciNetCrossRefMATH

Joux A.: A one round protocol for tripartite Diffie–Hellman. J. Cryptol. 17(4), 263–276 (2004).MathSciNetCrossRefMATH

Escala A., Herold G., Kiltz E., Ràfols C., Villar J.L.: An algebraic framework for Diffie–Hellman assumptions. J. Cryptol. 30(1), 242–288 (2017).MathSciNetCrossRefMATH

Bresson E., Chevassut O., Pointcheval D.: Provably secure authenticated group Diffie–Hellman key exchange. ACM Trans. Inf. Syst. Secur. 10(3), 10 (2007).CrossRefMATH

Mahassni E.E., Shparlinski I.: Polynomial representations of the Diffie–Hellman mapping. Bull. Aust. Math. Soc. 63, 467–473 (2001).MathSciNetCrossRefMATH

Winterhof A.: A note on the interpolation of the Diffie–Hellman mapping. Bull. Austral. Math. Soc. 64(3), 475–477 (2001).MathSciNetCrossRefMATH

10.

Kiltz E., Winterhof A.: On the interpolation of bivariate polynomials related to Diffie–Hellman mapping. Bull. Aust. Math. Soc. 69, 305–315 (2004).MathSciNetCrossRefMATH

11.

Shparlinski I.: Cryptographic Applications of Analytic Number Theory. Complexity Lower Bounds and Pseudorandomness. Birkhauser Verlag, Basel (2003).CrossRefMATH

12.

Ling S., Shparlinski I.E., Wang H.: On the multidimensional distribution of the Naor–Reingold pseudo-random function. Math. Comput. 83(289), 2429–2434 (2014).MathSciNetCrossRefMATH

13.

Shparlinski I.E.: On the Naor–Reingold pseudo-random function from elliptic curves. Appl. Algebra Eng. Commun. Comput. 11(1), 27–34 (2000).MathSciNetCrossRefMATH

14.

Ibeas À.: On the period of the Naor–Reingold sequence. Inf. Process. Lett. 108(5), 304–307 (2008).MathSciNetCrossRefMATH

15.

Gómez D., Gutierrez J., Ibeas A.: On the linear complexity of the Naor–Reingold sequence. Inf. Process. Lett. 111(17), 854–856 (2011).MathSciNetCrossRefMATH

16.

Shparlinski I.E.: Linear complexity of the Naor–Reingold pseudo-random function. Inf. Process. Lett. 76(3), 95–99 (2000).MathSciNetCrossRefMATH

17.

Shparlinski I.E., Silverman J.H.: On the linear complexity of the Naor–Reingold pseudo-random function from elliptic curves. Des. Codes Cryptogr. 24(3), 279–289 (2001).MathSciNetCrossRefMATH

18.

Cruz M., Gómez D., Sadornil D.: On the linear complexity of the Naor–Reingold sequence with elliptic curves. Finite Fields Appl. 16(5), 329–333 (2010).MathSciNetCrossRefMATH

19.

Banks W.D., Griffin F., Lieman D., Shparlinski I.: Non-linear complexity of the Naor–Reingold pseudo-random function. In: Song J. (ed.) ICISC 99: 2nd International Conference on Information Security and Cryptology, vol. 1787, pp. 53–59. Lecture Notes in Computer ScienceSpringer, Heidelberg, Germany, Seoul, Korea (2000).CrossRef

20.

Mefenza T., Vergnaud D.: Polynomial interpolation of the Naor–Reingold pseudo-random function. Appl. Algebra Eng. Commun. Comput. 28, 237–255 (2017).MathSciNetCrossRefMATH

21.

Coppersmith D., Shparlinski I.: On polynomial approximation of the discrete logarithm and the Diffie–Hellman mapping. J. Cryptol. 13(3), 339–360 (2000).MathSciNetCrossRefMATH

22.

Kiltz E., Winterhof A.: Polynomial interpolation of cryptographic functions related to Diffie–Hellman and discrete logarithm problem. Discret. Appl. Math. 154(2), 326–336 (2006).MathSciNetCrossRefMATH

23.

Lange, T., Winterhof, A.: Polynomial interpolation of the elliptic curve and XTR discrete logarithm. In: Ibarra, O.H., Zhang, L. (eds.) Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15–17, 2002. Lecture Notes in Computer Science, Vol. 2387, pp. 137–143. Springer (2002).

24.

Lange T., Winterhof A.: Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\). Discret. Appl. Math. 128(1), 193–206 (2003).CrossRefMATH

25.

Meletiou, G.C., Winterhof, A.: Interpolation of the double discrete logarithm. In: von zur Gathen, J. Imaña, J.L., Koç, Ç.K. (eds.) Arithmetic of Finite Fields, 2nd International Workshop, WAIFI 2008, Siena, Italy, July 6–9, 2008. Lecture Notes in Computer Science, Vol. 5130, pp. 1–10. Springer (2008).

Titel: Polynomial interpolation of the generalized Diffie–Hellman and Naor–Reingold functions
verfasst von: Thierry Mefenza
Damien Vergnaud
Publikationsdatum: 02.05.2018
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1/2019
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-018-0486-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1/2019

Sets of mutually orthogonal Sudoku frequency squares

Phased unitary Golay pairs, Butson Hadamard matrices and a conjecture of Ito’s

New results on the state cycles of Trivium

How many weights can a linear code have?

Improved bounds on 2-frameproof codes with length 4

Secure simultaneous bit extraction from Koblitz curves