Abstract
Let 
p
be a finite field of p elements, where p is prime. The bit security of the Diffie-Hellman function over subgroups of
*
p
and of an elliptic curve over
p
, is considered. It is shown that if the Decision Diffie-Hellman problem is hard in these groups, then the two most significant bits of the Diffie-Hellman function are secure. Under the weaker assumption of the computational (rather than decisional) hardness of the Diffie-Hellman problems, only about (log p)1/2 bits are known to be secure.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Blake, I.F., Garefalakis, T.: On the complexity of the discrete logarithm and Diffie-Hellman problems. J. Compl. 20, 148–170 (2004)
Blake, I.F., Seroussi, G., Smart, N.: Elliptic curves in cryptography. London Math. Soc., Lecture Note Series, Vol.265, Cambridge University Press 1999
Boneh, D., Shparlinski, I.E.: On the unpredictability of bits of the elliptic curve Diffie–Hellman scheme. Lect. Notes in Comp. Sci. Springer-Verlag, Berlin, 2139, 201–212 (2001)
Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of secret keys in Diffie–Hellman and related schemes. Lect. Notes in Comp. Sci. Springer-Verlag, Berlin, 1109, 129–142 (1996)
Bourgain, J., Konyagin, S.V.: Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order. Comptes Rendus Mathematique 337, 75–80 (2003)
Gennaro, R., Krawczyk, H., Rabin, T.: Hashed Diffie-Hellman over non-DDH groups. Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 3027, 361–381 (2004)
González Vasco, M.I., Näslund, M., Shparlinski, I.E.: The hidden number problem in extension fields and its applications. Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2286, 105–117 (2002)
González Vasco M.I., Näslund, M., Shparlinski I.E.: New results on the hardness of Diffie-Hellman bits. Proc. Intern. Workshop on Public Key Cryptography, Singapore, 2004. Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2947, 159–172 (2004)
González Vasco, M.I., Shparlinski, I.E.: On the security of Diffie-Hellman bits. Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 257–268
Heath-Brown, D.R., Konyagin, S.V.: New bounds for Gauss sums derived from kth powers, and for Heilbronn's exponential sum. Ouart. J. Math. 51, 221–235 (2000)
Joux, A., Nguyen, K.: Separating decision Diffie-Hellman from Diffie-Hellman in cryptographic groups. J. Cryptology 16, 239–247 (2003)
Kohel, D.R., Shparlinski, I.E.: Exponential sums and group generators for elliptic curves over finite fields. Lect. Notes in Comp. Sci. Springer-Verlag, Berlin, 1838, 395–404 (2000)
Konyagin, S.V., Shparlinski, I.: Character sums with exponential functions and their applications. Cambridge Univ. Press, Cambridge, 1999
Li, W.-C.W., Näslund, M., Shparlinski, I.E.: The hidden number problem with the trace and bit security of XTR and LUC. Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2442, 433–448 (2002)
Shparlinski, I.E.: Cryptographic applications of analytic number theory. Birkhäuser, 2003
Shparlinski, I.E.: Security of polynomial transformations of the Diffie-Hellman key. Finite Fields and Their Appl. 10, 123–131 (2004)
Shparlinski, I.E., Winterhof, A.: A hidden number problem in smal subgroups, Math. Comp., 74, 2073–2080 (2005), 1–12
Silverman, J.H.: The arithmetic of elliptic curves. Springer-Verlag, Berlin, 1995
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Blake, I., Garefalakis, T. & Shparlinski, I. On the bit security of the Diffie-Hellman key. AAECC 16, 397–404 (2006). https://doi.org/10.1007/s00200-005-0184-x
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00200-005-0184-x