### Abstract

Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a hidden element α ∈ double-struck F sign_{p}, where p is prime, from rather short strings of the most significant bits of the residue of at modulo p for several randomly chosen t ∈ double-struck F sign_{p}. González Vasco and the first author have recently extended this result to subgroups of double-struck F sign*_{p} of order at least p^{1/3+ε} for all p and to subgroups of order at least p^{ε} for almost all p. Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the multipliers t and thus extend this result to subgroups of order at least (log p)/(log log p)^{1-ε} for all primes p. As in the above works, we give applications of our result to the bit security of the Diffie-Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups.

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

Pages (from-to) | 2073-2080 |

Number of pages | 8 |

Journal | Mathematics of Computation |

Volume | 74 |

Issue number | 252 |

DOIs | |

Publication status | Published - Oct 2005 |

### Bibliographical note

Copyright [2005] American Mathematical Society. First published in Mathematics of Computation, 74:252, published by the American Mathematical Society. The original article can be found at http://dx.doi.org/10.1090/S0025-5718-05-01797-7.## Fingerprint Dive into the research topics of 'A hidden number problem in small subgroups'. Together they form a unique fingerprint.

## Cite this

*Mathematics of Computation*,

*74*(252), 2073-2080. https://doi.org/10.1090/S0025-5718-05-01797-7