Cryptology ePrint Archive: Report 2000/024
Security of the Most Significant Bits of the Shamir Message Passing Scheme
Maria Isabel Gonzalez Vasco and Igor E. Shparlinski
Abstract: Boneh and Venkatesan have recently proposed a polynomial time
algorithm for recovering a ``hidden'' element $\alpha$ of a
finite field $\F_p$ of $p$ elements from rather short
strings of the most significant bits of the remainder
mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected uniformly
at random from $\F_p^*$. 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
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.
Category / Keywords: public-key cryptography /
Date: received 25 May 2000
Contact author: igor at ics mq edu au
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Version: 20000526:011451 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]