Skip to main content
Top
Published in: Applicable Algebra in Engineering, Communication and Computing 5/2022

23-11-2020 | Original Paper

On the index of the Diffie–Hellman mapping

Authors: Leyla Işık, Arne Winterhof

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 5/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Let \(\gamma\) be a generator of a cyclic group G of order n. The least index of a self-mapping f of G is the index of the largest subgroup U of G such that \(f(x)x^{-r}\) is constant on each coset of U for some positive integer r. We determine the index of the univariate Diffie–Hellman mapping \(d(\gamma ^a)=\gamma ^{a^2}\), \(a=0,1,\ldots ,n-1\), and show that any mapping of small index coincides with d only on a small subset of G. Moreover, we prove similar results for the bivariate Diffie–Hellman mapping \(D(\gamma ^a,\gamma ^b)=\gamma ^{ab}\), \(a,b=0,1,\ldots ,n-1\). In the special case that G is a subgroup of the multiplicative group of a finite field we present improvements.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Akbary, A., Ghioca, D., Wang, Q.: On permutation polynomials of prescribed shape. Finite Fields Appl. 15(2), 195–206 (2009)MathSciNetCrossRef Akbary, A., Ghioca, D., Wang, Q.: On permutation polynomials of prescribed shape. Finite Fields Appl. 15(2), 195–206 (2009)MathSciNetCrossRef
2.
go back to reference Bach, E., Shallit, J.: Algorithmic Number Theory. MIT Press, Cambridge (1996)MATH Bach, E., Shallit, J.: Algorithmic Number Theory. MIT Press, Cambridge (1996)MATH
3.
go back to reference Blake, I.F., Garefalakis, T.: On the complexity of the discrete logarithm and Diffie–Hellman problems. J. Complex. 20(2–3), 148–170 (2004)MathSciNetCrossRef Blake, I.F., Garefalakis, T.: On the complexity of the discrete logarithm and Diffie–Hellman problems. J. Complex. 20(2–3), 148–170 (2004)MathSciNetCrossRef
4.
go back to reference Blake, I.F., Garefalakis, T.: Polynomial approximation of bilinear Diffie–Hellman maps. Finite Fields Appl. 14(2), 379–389 (2008)MathSciNetCrossRef Blake, I.F., Garefalakis, T.: Polynomial approximation of bilinear Diffie–Hellman maps. Finite Fields Appl. 14(2), 379–389 (2008)MathSciNetCrossRef
5.
go back to reference Coppersmith, D., Shparlinski, I.: On polynomial approximation of the discrete logarithm and the Diffie–Hellman mapping. J. Cryptol. 13(3), 339–360 (2000)MathSciNetCrossRef Coppersmith, D., Shparlinski, I.: On polynomial approximation of the discrete logarithm and the Diffie–Hellman mapping. J. Cryptol. 13(3), 339–360 (2000)MathSciNetCrossRef
6.
go back to reference El Mahassni, E., Shparlinski, I.: Polynomial representations of the Diffie–Hellman mapping. Bull. Aust. Math. Soc. 63(3), 467–473 (2001)MathSciNetCrossRef El Mahassni, E., Shparlinski, I.: Polynomial representations of the Diffie–Hellman mapping. Bull. Aust. Math. Soc. 63(3), 467–473 (2001)MathSciNetCrossRef
7.
go back to reference Işık, L., Winterhof, A.: Carlitz rank and index of permutation polynomials. Finite Fields Appl. 49, 156–165 (2018)MathSciNetCrossRef Işık, L., Winterhof, A.: Carlitz rank and index of permutation polynomials. Finite Fields Appl. 49, 156–165 (2018)MathSciNetCrossRef
8.
go back to reference Kiltz, E., Winterhof, A.: On the interpolation of bivariate polynomials related to the Diffie–Hellman mapping. Bull. Aust. Math. Soc. 69(2), 305–315 (2004)MathSciNetCrossRef Kiltz, E., Winterhof, A.: On the interpolation of bivariate polynomials related to the Diffie–Hellman mapping. Bull. Aust. Math. Soc. 69(2), 305–315 (2004)MathSciNetCrossRef
9.
go back to reference Kiltz, E., Winterhof, A.: Polynomial interpolation of cryptographic functions related to Diffie–Hellman and discrete logarithm problem. Discr. Appl. Math. 154(2), 326–336 (2006)MathSciNetCrossRef Kiltz, E., Winterhof, A.: Polynomial interpolation of cryptographic functions related to Diffie–Hellman and discrete logarithm problem. Discr. Appl. Math. 154(2), 326–336 (2006)MathSciNetCrossRef
10.
go back to reference Konjagin, V.S.: The number of solutions of congruences of the nth degree with one unknown. Mat. Sb. (N.S.) 109(151)(2), 171–187, 327 (1979). (Russian)MathSciNet Konjagin, V.S.: The number of solutions of congruences of the nth degree with one unknown. Mat. Sb. (N.S.) 109(151)(2), 171–187, 327 (1979). (Russian)MathSciNet
11.
go back to reference Lange, T., Winterhof, A.: Polynomial interpolation of the elliptic curve and XTR discrete logarithm. In: Computing and combinatorics, Lecture Notes in Computer Science, vol. 2387, pp. 137–143. Springer, Berlin (2002) Lange, T., Winterhof, A.: Polynomial interpolation of the elliptic curve and XTR discrete logarithm. In: Computing and combinatorics, Lecture Notes in Computer Science, vol. 2387, pp. 137–143. Springer, Berlin (2002)
12.
go back to reference Lange, T., Winterhof, A.: Interpolation of the elliptic curve Diffie–Hellman mapping. In: Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 2003), Lecture Notes in Computer Science, vol. 2643, pp. 51–60. Springer, Berlin (2003) Lange, T., Winterhof, A.: Interpolation of the elliptic curve Diffie–Hellman mapping. In: Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 2003), Lecture Notes in Computer Science, vol. 2643, pp. 51–60. Springer, Berlin (2003)
13.
go back to reference Mefenza, T., Vergnaud, D.: Polynomial interpolation of the generalized Diffie–Hellman and Naor–Reingold functions. Des. Codes Cryptogr. 87(1), 75–85 (2019)MathSciNetCrossRef Mefenza, T., Vergnaud, D.: Polynomial interpolation of the generalized Diffie–Hellman and Naor–Reingold functions. Des. Codes Cryptogr. 87(1), 75–85 (2019)MathSciNetCrossRef
14.
go back to reference Meidl, W., Winterhof, A.: A polynomial representation of the Diffie–Hellman mapping. Appl. Alg. Eng. Commun. Comput. 13, 313–318 (2002)MathSciNetCrossRef Meidl, W., Winterhof, A.: A polynomial representation of the Diffie–Hellman mapping. Appl. Alg. Eng. Commun. Comput. 13, 313–318 (2002)MathSciNetCrossRef
15.
go back to reference Mullen, G.L., Wan, D., Wang, Q.: Index Bounds for Value Sets of Polynomials Over Finite Fields, Applied Algebra and Number Theory, pp. 280–296. Cambridge University Press, Cambridge (2014)MATH Mullen, G.L., Wan, D., Wang, Q.: Index Bounds for Value Sets of Polynomials Over Finite Fields, Applied Algebra and Number Theory, pp. 280–296. Cambridge University Press, Cambridge (2014)MATH
16.
go back to reference Niederreiter, H., Winterhof, A.: Cyclotomic \({\cal{R}}\)-orthomorphisms of finite fields. Discr. Math. 295, 161–171 (2005)MathSciNetCrossRef Niederreiter, H., Winterhof, A.: Cyclotomic \({\cal{R}}\)-orthomorphisms of finite fields. Discr. Math. 295, 161–171 (2005)MathSciNetCrossRef
17.
go back to reference Niederreiter, H., Winterhof, A.: Applied Number Theory. Springer, Cham (2015)CrossRef Niederreiter, H., Winterhof, A.: Applied Number Theory. Springer, Cham (2015)CrossRef
18.
go back to reference Shparlinski, I.: Cryptographic Applications of Analytic Number Theory. Complexity Lower Bounds and Pseudorandomness, Progr. Comput. Sc. Appl. Logic, vol. 22. Birkhäuser Verlag, Basel (2003) Shparlinski, I.: Cryptographic Applications of Analytic Number Theory. Complexity Lower Bounds and Pseudorandomness, Progr. Comput. Sc. Appl. Logic, vol. 22. Birkhäuser Verlag, Basel (2003)
19.
go back to reference Wang, Q.: Cyclotomic mapping permutation polynomials over finite fields. In: Sequences, Subsequences, and Consequences (International Workshop, SSC 2007, Los Angeles, CA, USA, May 31–June 2, 2007), Lecture Notes in Computer Sciene, vol. 4893, pp. 119–128. Springer, Berlin (2007) Wang, Q.: Cyclotomic mapping permutation polynomials over finite fields. In: Sequences, Subsequences, and Consequences (International Workshop, SSC 2007, Los Angeles, CA, USA, May 31–June 2, 2007), Lecture Notes in Computer Sciene, vol. 4893, pp. 119–128. Springer, Berlin (2007)
20.
go back to reference Wang, Q.: Polynomials over finite fields: an index approach. In: Combinatorics and Finite Fields: Difference Sets, Polynomials, Pseudorandomness and Applications, Radon Series. Comput. Appl. Math. vol. 23, pp. 319–348. de Gruyter, Berlin/Boston (2019) Wang, Q.: Polynomials over finite fields: an index approach. In: Combinatorics and Finite Fields: Difference Sets, Polynomials, Pseudorandomness and Applications, Radon Series. Comput. Appl. Math. vol. 23, pp. 319–348. de Gruyter, Berlin/Boston (2019)
21.
Metadata
Title
On the index of the Diffie–Hellman mapping
Authors
Leyla Işık
Arne Winterhof
Publication date
23-11-2020
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 5/2022
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-020-00475-3

Other articles of this Issue 5/2022

Applicable Algebra in Engineering, Communication and Computing 5/2022 Go to the issue

Premium Partner