**On the Security of Diffie--Hellman Bits**

*Maria Isabel Gonzalez Vasco and Igor E. Shparlinski*

**Abstract: **Boneh and Venkatesan have recently proposed a polynomial time
algorithm for recovering a "hidden" element $\alpha$ of a finite field $\F_p$ of $p$ elements from rather short strings of the most significant bits of the remainder modulo $p$ of $\alpha t$ for several
values of $t$ selected uniformly at random from $\F_p^*$. We use some
recent bounds of exponential sums to generalize this algorithm to the case when $t$ is selected from a quite small subgroup of $\F_p^*$.
Namely, our results apply to subgroups of size at least
$p^{1/3+ \varepsilon}$ for all primes $p$ and to subgroups of size at
least $p^{\varepsilon}$ for almost all primes $p$, for any fixed
$\varepsilon >0$.

We also use this generalization to improve (and correct) one of the statements of the aforementioned work about the computational security of the most significant bits of the Diffie--Hellman key.

**Category / Keywords: **public-key cryptography / Diffie-Hellman, Exponential Sums

**Date: **received 18 May 2000

**Contact author: **igor at comp mq edu au

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20000525:165818 (All versions of this report)

**Short URL: **ia.cr/2000/020

[ Cryptology ePrint archive ]