# Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes

**Authors:**

*D. Boneh and R. Venkatesan*

** 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 *O _{α}(x)* that on input

*x*computes the

*k*most significant bits of (α * g

^{x}mod p) , find

*α mod p*. Our solution can be used to show the hardness of \msb's in other schemes such s ElGamal's public key system, Shamir's message passing scheme and Okamoto's conference key sharing 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.

** Reference:**

In Proceedings *Crypto '96*,
Lecture Notes in Computer Science, Vol. 1109, Springer-Verlag,
pp. 129--142, 1996

**Full paper:**
PostScript