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
DOI: https://doi.org/10.1090/S0025-5718-01-01358-8
Published electronically: June 14, 2001
MathSciNet review: 1863004
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract:

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?)

  • 1. D. Boneh and R. Venkatesan, Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1109 (1996), 129-142.
  • 2. M. I. González Vasco and M. Näslund, A survey of hard core functions, Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 227-256.
  • 3. M. I. González Vasco and I. E. Shparlinski, On the security of Diffie-Hellman bits, Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 257-268.
  • 4. S. V. Konyagin and I. E. Shparlinski, Character sums with exponential functions and their applications, Cambridge Univ. Press, Cambridge, 1999.MR 2000h:11089
  • 5. A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 515-534. MR 84a:12002
  • 6. R. Kannan, Algorithmic geometry of numbers, Annual Review of Comp. Sci., 2 (1987), 231-267. MR 89a:11131
  • 7. N. M. Korobov, `On the distribution of digits in periodic fractions', Math. USSR - Sbornik, 18 (1972), 659-676. MR 59:12619
  • 8. D. Micciancio, On the hardness of the shortest vector problem, PhD Thesis, MIT, 1998.
  • 9. A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, FL, 1997. MR 99g:94015
  • 10. P. Nguyen and J. Stern, Lattice reduction in cryptology: An update, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1838 (2000), 85-112.
  • 11. H. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc., 84 (1978), 957-1041. MR 80d:65016
  • 12. K. Prachar, Primzahlverteilung, Springer-Verlag, Berlin, 1957. MR 19:393b
  • 13. C. P. Schnorr, A hierarchy of polynomial time basis reduction algorithms, Theor. Comp. Sci., 53 (1987), 201-224. MR 89h:11085
  • 14. I. M. Vinogradov, Elements of number theory, Dover Publ., New York, 1954. MR 19:933e

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
Email: mvasco@orion.ciencias.uniovi.es

Igor E. Shparlinski
Affiliation: Dept. of Computing, Macquarie University, Sydney, NSW 2109, Australia
Email: igor@ics.mq.edu.au

DOI: https://doi.org/10.1090/S0025-5718-01-01358-8
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

American Mathematical Society