On the bit security of the weak Diffie–Hellman problem

Boneh and Venkatesan proposed a problem called the hidden number problem and they gave a polynomial time algorithm to solve it. And they showed that one can compute gxy from gx and gy if one has an oracle which computes roughly most significant bits of gxy from given gx and gy in Fp by using an algorithm for solving the hidden number problem. Later, Shparlinski showed that one can compute gx2 if one can compute roughly most significant bits of gx2 from given gx. In this paper we extend these results by using some improvements on the hidden number problem and the bound of exponential sums. We show that for given , computing about most significant bits of g1/α is as hard as computing g1/α itself, provided that the multiplicative order of g is prime and not too small. Furthermore, we show that we can do it when g has even much smaller multiplicative order in some special cases.