## Abstract

Boneh and Venkatesan have proposed a polynomial time algorithm in a non-uniform model for recovering a "hidden" element α ∈ F_{p}, where p is prime, from very short strings of the most significant bits of the residue of αt modulo p for several randomly chosen t ∈ F_{p}. Here we modify the scheme and amplify the uniformity of distribution of the 'multipliers' t and thus extend this result to subgroups of F_{p}*, which are more relevant to practical usage. As in the work of Boneh and Venkatesan, our result can be applied to the bit security of Diffie-Hellman related encryption schemes starting with subgroups of very small size, including all cryptographically interesting subgroups.

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

Pages (from-to) | 416-424 |

Number of pages | 9 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 2947 |

Publication status | Published - 2004 |

## Keywords

- Diffie-Hellman key exchange
- Exponential sums
- Hidden number problem
- Lattice reduction
- Nonuniform algorithm
- Waring problem in finite fields