Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes

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 {em hidden number problem}: Given an
oracle $O_{alpha,eta}(x)$ that on input $x$ computes the $k$ most
significant bits of $alpha g^x + eta mod p $, find $alpha, eta
mod p$. We present many other applications of this problem
including: (1) MSB's in El-Gamal encryptions, Shamir Message passing
scheme etc. are hard to compute. (2) Factoring with hints. Our
results lead us to suggest a new variant of Diffie-Hellman key
exchange, for which we prove the most significant bit is hard to
compute.