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

Authors: D. Boneh and R. Venkatesan

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 (α * gx 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.

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

Full paper: PostScript