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 (α * 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.
Reference:
In Proceedings Crypto '96,
Lecture Notes in Computer Science, Vol. 1109, Springer-Verlag,
pp. 129--142, 1996
Full paper: PostScript