International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Security of the Most Significant Bits of the Shamir Message Passing Scheme

Authors:
Maria Isabel Gonzalez Vasco
Igor E. Shparlinski
Download:
URL: http://eprint.iacr.org/2000/024
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2000-11368,
  title={Security of the Most Significant Bits of the Shamir Message Passing Scheme},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography /},
  url={http://eprint.iacr.org/2000/024},
  note={ igor@ics.mq.edu.au 11103 received 25 May 2000},
  author={Maria Isabel Gonzalez Vasco and Igor E. Shparlinski},
  year=2000
}