Security of most significant bits of gx(2)

Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a "hidden" element α of a finite field (double-struck F sign)p = {0, ..., p-1} of p elements from rather short strings of the most significant bits of the remainder modulo p of αt for several values of t selected uniformly at random from (double-struck F sign)p *. González Vasco and Shparlinski, using bounds of exponential sums, have generalized this algorithm to the case where t is selected from a subgroup of (double-struck F sign) p *. In turn, this has allowed to improve one of the statements of the aforementioned work about the security of the most significant bits of the Diffie-Hellman key. Namely, it has been shown that having an oracle which, given gx, gy ∈ (double-struck F sign)p * for returns about log1/2 p most significant bits of gxy ∈ (double-struck F sign)p *, one can construct a polynomial time algorithm to compute gxy, provided that the multiplicative order of g is not too small. Here we use exponential sums of a different type to show that a similar statement holds for a much weaker 'diagonal' oracle which which, given gx ∈ (double struck F sign)p *, returns about log1/2 p most significant bits of gx(2) ∈ (double-struck F sign)p *.

Original languageEnglish
Pages (from-to)109-113
Number of pages5
JournalInformation Processing Letters
Issue number2
Publication statusPublished - 31 Jul 2002


Dive into the research topics of 'Security of most significant bits of gx(2)'. Together they form a unique fingerprint.

Cite this