@inproceedings{de16705af6154bfdb85acfb2bcddb268,

title = "On the security of Diffie-Hellman bits",

abstract = "Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a {"}hidden{"} element a: of a finite field IFp of p elements from rather short strings of the most significant bits of the remainder module p of at for several values of t selected uniformly at random from IFp*. We use some recent bounds of exponential sums to generalize this algorithm to the case when t is selected from a quite small subgroup of IFp*. Namely, our results apply to subgroups of size at least p(1/3+E) for all primes p and to subgroups of size at least p(epsilon) for almost all primes p, for any fixed epsilon > 0. We also use this generalization to improve (and correct) one of the statements of the aforementioned work about the computational security of the most significant bits of the Diffie-Hellman key.",

keywords = "REDUCTION, NUMBERS",

author = "Vasco, {Mar{\'i}a Isabel Gonz{\'a}lez} and IE Shparlinski",

year = "2001",

doi = "10.1007/978-3-0348-8295-8_19",

language = "English",

isbn = "3764365102",

series = "Progress in Computer Science and Applied Logic",

publisher = "Birkhauser Verlag Basel",

pages = "257--268",

editor = "Lam, {K. Y.} and Igor Shparlinski and H. Wang and Xing, {C. P.}",

booktitle = "Cryptography and computational number theory",

address = "Switzerland",

note = "Workshop on Cryptography and Computational Number Theory (CCNT 99) ; Conference date: 22-11-1999 Through 26-11-1999",

}