Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Security of the most significant bits of the Shamir message passing scheme

Authors: Maria Isabel González Vasco and Igor E. Shparlinski
Journal: Math. Comp. 71 (2002), 333-342
MSC (2000): Primary 94A60; Secondary 11T23, 11T71
Published electronically: June 14, 2001
MathSciNet review: 1863004
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


Boneh and Venkatesan have recently proposed a polynomial time algorithm for recovering a ``hidden'' element $\alpha$ of a finite field $\mathbb{F}_p$ of $p$ elements from rather short strings of the most significant bits of the remainder modulo $p$ of $\alpha t$ for several values of $t$ selected uniformly at random from $\mathbb{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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 94A60, 11T23, 11T71

Retrieve articles in all journals with MSC (2000): 94A60, 11T23, 11T71

Additional Information

Maria Isabel González Vasco
Affiliation: Department of Mathematics, University of Oviedo, Oviedo, 33007, Spain

Igor E. Shparlinski
Affiliation: Dept. of Computing, Macquarie University, Sydney, NSW 2109, Australia

Keywords: Shamir message passing scheme, bit security, exponential sums, cryptography
Received by editor(s): May 18, 2000
Published electronically: June 14, 2001
Article copyright: © Copyright 2001 American Mathematical Society