TY - JOUR

T1 - A hidden number problem in small subgroups

AU - Shparlinski, Igor

AU - Winterhof, Arne

N1 - 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.

PY - 2005/10

Y1 - 2005/10

N2 - Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a hidden element α ∈ double-struck F signp, 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 signp. González Vasco and the first author have recently extended this result to subgroups of double-struck F sign*p of order at least p1/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.

AB - Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a hidden element α ∈ double-struck F signp, 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 signp. González Vasco and the first author have recently extended this result to subgroups of double-struck F sign*p of order at least p1/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.

UR - http://www.scopus.com/inward/record.url?scp=27144457646&partnerID=8YFLogxK

U2 - 10.1090/S0025-5718-05-01797-7

DO - 10.1090/S0025-5718-05-01797-7

M3 - Article

AN - SCOPUS:27144457646

SN - 0025-5718

VL - 74

SP - 2073

EP - 2080

JO - Mathematics of Computation

JF - Mathematics of Computation

IS - 252

ER -