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_{\alpha}(x) that on input x computes the k
most significant bits of \alpha * g^x mod p , find \alpha
modulo 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