TY - JOUR
T1 - Security of most significant bits of gx(2)
AU - Shparlinski, Igor E.
PY - 2002/7/31
Y1 - 2002/7/31
N2 - Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a "hidden" element α of a finite field (double-struck F sign)p = {0, ..., p-1} of p elements from rather short strings of the most significant bits of the remainder modulo p of αt for several values of t selected uniformly at random from (double-struck F sign)p *. González Vasco and Shparlinski, using bounds of exponential sums, have generalized this algorithm to the case where t is selected from a subgroup of (double-struck F sign) p *. In turn, this has allowed to improve one of the statements of the aforementioned work about the security of the most significant bits of the Diffie-Hellman key. Namely, it has been shown that having an oracle which, given gx, gy ∈ (double-struck F sign)p * for returns about log1/2 p most significant bits of gxy ∈ (double-struck F sign)p *, one can construct a polynomial time algorithm to compute gxy, provided that the multiplicative order of g is not too small. Here we use exponential sums of a different type to show that a similar statement holds for a much weaker 'diagonal' oracle which which, given gx ∈ (double struck F sign)p *, returns about log1/2 p most significant bits of gx(2) ∈ (double-struck F sign)p *.
AB - Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a "hidden" element α of a finite field (double-struck F sign)p = {0, ..., p-1} of p elements from rather short strings of the most significant bits of the remainder modulo p of αt for several values of t selected uniformly at random from (double-struck F sign)p *. González Vasco and Shparlinski, using bounds of exponential sums, have generalized this algorithm to the case where t is selected from a subgroup of (double-struck F sign) p *. In turn, this has allowed to improve one of the statements of the aforementioned work about the security of the most significant bits of the Diffie-Hellman key. Namely, it has been shown that having an oracle which, given gx, gy ∈ (double-struck F sign)p * for returns about log1/2 p most significant bits of gxy ∈ (double-struck F sign)p *, one can construct a polynomial time algorithm to compute gxy, provided that the multiplicative order of g is not too small. Here we use exponential sums of a different type to show that a similar statement holds for a much weaker 'diagonal' oracle which which, given gx ∈ (double struck F sign)p *, returns about log1/2 p most significant bits of gx(2) ∈ (double-struck F sign)p *.
UR - http://www.scopus.com/inward/record.url?scp=0037205807&partnerID=8YFLogxK
U2 - 10.1016/S0020-0190(01)00315-5
DO - 10.1016/S0020-0190(01)00315-5
M3 - Article
AN - SCOPUS:0037205807
SN - 0020-0190
VL - 83
SP - 109
EP - 113
JO - Information Processing Letters
JF - Information Processing Letters
IS - 2
ER -