Abstract
Let \( {\mathbb{E} \mathord{\left/ {\vphantom {\mathbb{E} \mathbb{F}}} \right. \kern-\nulldelimiterspace} \mathbb{F}}_p \) be an elliptic curve, and \( {\mathbb{E} \mathord{\left/ {\vphantom {\mathbb{E} \mathbb{F}}} \right. \kern-\nulldelimiterspace} \mathbb{F}}_p \). Define the Diffie-Hellman function as DH E,G (aG,bG) = abG. We show that if there is an efficient algorithm for predicting the LSB of the x or y coordinate of abG given \( \left\langle \mathbb{E} \right.,G,\left. {aG,bG} \right\rangle \) for a certain family of elliptic curves, then there is an algorithm for computing the Diffie-Hellman function on all curves in this family. This seems stronger than the best analogous results for the Diffie-Hellman function in \( \mathbb{F}_p^* \). Boneh and Venkatesan showed that in \( \mathbb{F}_p^* \) computing approximately (log p)1/2 of the bits of the Diffie-Hellman secret is as hard as computing the entire secret. Our results show that just predicting one bit of the Elliptic Curve Diffie-Hellman secret in a family of curves is as hard as computing the entire secret.
Supported by NSF and the Packard Foundation.
Supported in part by ARC
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
W. Alexi, B. Chor, O. Goldreich, and C. Schnorr. ‘RSA and Rabin functions: Certain parts are as hard as the whole’, SIAM J. Computing, 17(1988), 194–209, Nov. 1988.
I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography, London Mathematical Society, Lecture Notes Series, 265, Cambridge University Press, 1999.
D. Boneh, ‘The decision Diffie-Hellman problem’, In Proc. 3rd Algorithmic Number Theory Symposium, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1423 (1998), 48–63.
D. Boneh, S. Halevi and N. A. Howgrave-Graham, ‘The modular inversion hidden number problem’, Preprint, 2001.
D. Boneh and R. Venkatesan, ‘Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes’, In Proc. Crypto’ 96, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1109 (1996), 129–142. Recent version available at http://crypto.stanford.edu/dabo/.
E. El Mahassni, P. Q. Nguyen and I. E. Shparlinski, ‘The insecurity of Nyberg-Rueppel and other DSA-like signature schemes with partially known nonces’, Proc. Workshop on Lattices and Cryptography, Boston, MA, 2001 (to appear).
R. Fischlin, C. Schnorr, ‘Stronger security proofs for RSA and Rabin bits’, J. Cryptology, 13 (2000), 221–244.
O. Goldreich, L. Levin, ‘A hard core predicate for any one way function’, In Proc. 21st ACM Symp. on Theory of Comput., 1989, 25–32.
M. I. González Vasco and M. Näslund, ‘A survey of hard core functions’, In Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 227–256.
M. I. González Vasco and I. E. Shparlinski, ‘On the security of Diffie-Hellman bits’, Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 257–268.
M. I. González Vasco and I. E. Shparlinski, ‘Security of the most significant bits of the Shamir message passing scheme’, Math. Comp. (to appear).
M. Naslund, ‘All bits in ax + b mod p are hard’, In Proc. Crypto’ 96, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1109 (1996), 114–128.
N. A. Howgrave-Graham and N. P. Smart, ‘Lattice attacks on digital signature schemes’, Designs, Codes and Cryptography (to appear).
N. A. Howgrave-Graham, P. Q. Nguyen and I. E. Shparlinski, ‘Hidden number problem with hidden multipliers, timed-release crypto and noisy exponentiation’, Preprint, 2000, 1–26.
A. J. Menezes, P. C. van Oorrschot and S. A. Vanstone, Handbook of applied cryptography, CRC Press, Boca Raton, FL, 1996.
P. Q. Nguyen, ‘The dark side of the hidden number problem: Lattice attacks on DSA’, Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 321–330.
P. Q. Nguyen and I. E. Shparlinski, ‘The insecurity of the Digital Signature Algorithm with partially known nonces’, Preprint, 2000, 1–26.
P. Q. Nguyen and I. E. Shparlinski, ‘The insecurity of the elliptic curve Digital Signature Algorithm with partially known nonces’, Preprint, 2000, 1–24.
P. Q. Nguyen and J. Stern, ‘Lattice reduction in cryptology: An update’, In Proc. 4th Algorithmic Number Theory Symposium, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1838 (2000), 85–112.
H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM, Philadelphia, 1992.
V. Shoup, ‘Lower bounds for discrete logarithms and related problems’, In Proc. Eurocrypt’ 97, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1233 (1997), 256–266.
I. E. Shparlinski, ‘Sparse polynomial approximation in finite fields’, Proc. 33rd ACM Symp. on Theory of Comput., Crete, Greece, July 6–8, 2001 (to appear).
I. E. Shparlinski, ‘On the generalized hidden number problem and bit security of XTR’, In Proc. the 14th Symp. on Appl. Algebra, Algebraic Algorithms, and Error-Correcting Codes, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin (to appear).
J. H. Silverman, The arithmetic of elliptic curves, Springer-Verlag, Berlin, 1995.
D. R. Stinson, Cryptography: Theory and practice, CRC Press, Boca Raton, FL, 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boneh, D., Shparlinski, I.E. (2001). On the Unpredictability of Bits of the Elliptic Curve Diffie-Hellman Scheme. In: Kilian, J. (eds) Advances in Cryptology — CRYPTO 2001. CRYPTO 2001. Lecture Notes in Computer Science, vol 2139. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44647-8_12
Download citation
DOI: https://doi.org/10.1007/3-540-44647-8_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42456-7
Online ISBN: 978-3-540-44647-7
eBook Packages: Springer Book Archive