Abstract
We show that computing the most significant bits of the secret key in a Diffie-Hellman key-exchange protocol from the public keys of the participants is as hard as computing the secret key itself. This is done by studying the following hidden number problem: Given an oracle \( \mathcal{O} \) α(x) that on input x computes the k most significant bits of α · g x mod p, find α modulo p. Our solution can be used to show the hardness of MSB’s in other schemes such s ElGamal’s public key system, scheme. Our results lead us to suggest a new variant of Diffie-Hellman key exchange (and other systems), for which we prove the most significant bit is hard to compute.
Chapter PDF
Similar content being viewed by others
Keywords
- Block Cipher
- Discrete Logarithm Problem
- Efficient Algorithm Computing
- Basis Reduction Algorithm
- Collision Resistant Hash Function
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(2):194–209, Nov. 1988.
L. Babai. On Lovasz’ lattice reduction and the nearest lattice point problem. Combinatorica, 6:1–13, 1986.
D. Bleichenbacher. Generating ElGamal Signatures without knowing the secret key EuroCrypt96, pp 10–18, 1996
D. Boneh, R. Venkatesan. Basis reduction with a matrix norm and its applications. Manuscript, 1996.
W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976.
T. El-Gamal. A public key cryptosystem and a signature scheme based on the discrete logarithm. IEEE Transactions on Information Theory, 31(4):469–472, 1985.
A. Frieze, J. Hastad, R. Kannan, J. Lagarias, and A. Shamir. Reconstructing Truncated Integer Variables Satisfying Linear Congruences. SIAM J. Computing, 17(2):262–280, 1988.
O. Goldreich, L.A. Levin. Hard core bits based on any one way function. In Proc. ACM Symp. on Theory of Computing 1989.
N. Koblitz. A course in number theory and cryptography. Springer-Verlag, 1987.
A. Lenstra, H. Lenstra, and L. Lovasz. Factoring polynomial with rational coefficients. Mathematiche Annalen, 261:515–534, 1982.
S. Micali M. Bellare. Non-interactive oblivious transfer and applications. In Proc. CRYPTO 89, pages 547–557, 1989.
T. Okamoto. Encryption and Authentication Schemes Based on Public Key Systems. PhD thesis, Univ. of Tokyo, 1988.
C, Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms Theoretical Computer Science, 53:201–224, 1987
C.P. Schnorr: Reduced Lattice Bases and Successive Minima. Combinatorics, Probability and Computing 3, (1994), 507–522.
K. Sakurai and H Shizuya. Relationships among the computational powers of breaking discrete log cryptosystems. In Proc. EUROCRYPT 95, pages 341–355, May 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boneh, D., Venkatesan, R. (1996). Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes. In: Koblitz, N. (eds) Advances in Cryptology — CRYPTO ’96. CRYPTO 1996. Lecture Notes in Computer Science, vol 1109. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68697-5_11
Download citation
DOI: https://doi.org/10.1007/3-540-68697-5_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61512-5
Online ISBN: 978-3-540-68697-2
eBook Packages: Springer Book Archive