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

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 $$ \mathcal{O} $$_α(x) that on input x computes the k most significant bits of α · gx mod p, find α modulo p. Our solution can be used to show the hardness of MSB’s in other schemes such s ElGamal’s public key system, 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.