## IACR paper details

Title | Hidden Number Problem in Small Subgroups |
---|

Booktitle | IACR Eprint archive |
---|

Pages | |
---|

Year | 2003 |
---|

URL | http://eprint.iacr.org/2003/049 |
---|

Author | Igor E. Shparlinski |
---|

Author | Arne Winterhof |
---|

Abstract |
Boneh and Venkatesan have proposed a polynomial time algorithm for
recovering a "hidden" element $\alpha \in \F_p$, where $p$ is prime, from rather short strings of the most significant bits of the residue of $\alpha t$ modulo $p$ for several randomly chosen $t\in \F_p$. Gonz{\'a}lez Vasco and the first author have recently extended this result to subgroups of $\F_p^*$ of order at least $p^{1/3+\varepsilon}$ for all $p$ and to subgroups of order at least $p^\varepsilon$ 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-\varepsilon}$ 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. |
---|

Search for the paper

@misc{eprint-2003-11766,
title={Hidden Number Problem in Small Subgroups},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / Hidden number problem, Exponential sums, Diffie-Hellman scheme,},
url={http://eprint.iacr.org/2003/049},
note={ igor@comp.mq.edu.au 12124 received 13 Mar 2003},
author={Igor E. Shparlinski and Arne Winterhof},
year=2003
}

Download a complete BibTeX file.