We study the hardness of computing the most significant bits of the secret key in a Diffie-Hellman key-exchange protocol from the public keys of the participants. Most of our techniques are based on lattices, specifically lattice reductions and rounding. In this talk we will survey our current state of knowledge on this topic including some new results. Our methods are general enough and can be used to prove the hardness of computing bits in other schemes related to Diffie-Hellman. Examples include ElGamal's public key system, Shamir's message passing scheme and Okamoto's conference key sharing scheme. Our results leads us to suggest a simple variant of the Diffie-Hellman key exchange, for which we prove the single most significant bit is hard to compute.
Joint work with R. Venkatesan.