## Abstract

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 g^{x}, g^{y} ∈ (double-struck F sign)_{p} ^{*} for returns about log^{1/2} p most significant bits of g^{xy} ∈ (double-struck F sign)_{p} ^{*}, one can construct a polynomial time algorithm to compute g^{xy}, 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 g^{x} ∈ (double struck F sign)_{p} ^{*}, returns about log^{1/2} p most significant bits of g^{x(2)} ∈ (double-struck F sign)_{p} ^{*}.

Original language | English |
---|---|

Pages (from-to) | 109-113 |

Number of pages | 5 |

Journal | Information Processing Letters |

Volume | 83 |

Issue number | 2 |

DOIs | |

Publication status | Published - 31 Jul 2002 |