TY - JOUR
T1 - Security of the most significant bits of the Shamir message passing scheme
AU - Vasco, Maria Isabel González
AU - Shparlinski, Igor E.
PY - 2002
Y1 - 2002
N2 - Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a "hidden" element a of a finite field Fp 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 Fp*. Unfortunately the applications to the computational security of most significant bits of private keys of some finite field exponentiation based cryptosystems given by Boneh and Venkatesan are not quite correct. For the Diffie-Hellman cryptosystem the result of Boneh and Venkatesan has been corrected and generalized in our recent paper. Here a similar analysis is given for the Shamir message passing scheme. The results depend on some bounds of exponential sums.
AB - Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a "hidden" element a of a finite field Fp 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 Fp*. Unfortunately the applications to the computational security of most significant bits of private keys of some finite field exponentiation based cryptosystems given by Boneh and Venkatesan are not quite correct. For the Diffie-Hellman cryptosystem the result of Boneh and Venkatesan has been corrected and generalized in our recent paper. Here a similar analysis is given for the Shamir message passing scheme. The results depend on some bounds of exponential sums.
UR - http://www.scopus.com/inward/record.url?scp=0036003397&partnerID=8YFLogxK
U2 - 10.1090/S0025-5718-01-01358-8
DO - 10.1090/S0025-5718-01-01358-8
M3 - Article
AN - SCOPUS:0036003397
SN - 0025-5718
VL - 71
SP - 333
EP - 342
JO - Mathematics of Computation
JF - Mathematics of Computation
IS - 237
ER -