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

Metadata
Available format(s)
PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
igor @ ics mq edu au
History
2000-05-26: received
Short URL
https://ia.cr/2000/024
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2000/024,
      author = {Maria Isabel Gonzalez Vasco and Igor E.  Shparlinski},
      title = {Security of the Most Significant Bits of the Shamir Message Passing Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2000/024},
      year = {2000},
      note = {\url{https://eprint.iacr.org/2000/024}},
      url = {https://eprint.iacr.org/2000/024}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.