Playing "hide-and-seek" with numbers: the hidden number problem, lattices and exponential sums

IE Shparlinski*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

We give a survey of recent results on the hidden number problem introduced by Boneh and Venkatesan in 1996 and its numerous generalizations. Many of the results in this area are based on a rather surprising combination of two celebrated number theoretic techniques: bounds of exponential sums and lattice basis reduction algorithms, which are briefly outlined as well. We also describe several cryptographic applications and outline some possible directions for further research.

Original languageEnglish
Title of host publicationPublic-key cryptography
EditorsP Garret, D Lieman
Place of PublicationProvidence
PublisherAmerican Mathematical Society
Pages153-177
Number of pages25
ISBN (Print)0821833650
Publication statusPublished - 2005
EventJoint Annual Meeting of the American-Mathematical-Society/Mathematical-Association-of-America - Baltimore, Moldova, Republic of
Duration: 17 Jan 2003 → …

Publication series

NameProceedings of Symposia in Applied Mathematics
PublisherAmerican Mathematical Society
Volume62
ISSN (Print)2324-7088

Conference

ConferenceJoint Annual Meeting of the American-Mathematical-Society/Mathematical-Association-of-America
CountryMoldova, Republic of
CityBaltimore
Period17/01/03 → …

Keywords

  • PARTIALLY KNOWN NONCES
  • DIGITAL SIGNATURE ALGORITHM
  • SPARSE POLYNOMIAL INTERPOLATION
  • PSEUDORANDOM BINARY SEQUENCES
  • DIFFIE-HELLMAN BITS
  • FINITE-FIELDS
  • QUADRATIC RESIDUES
  • SECURITY
  • GENERATORS
  • COMPLEXITY

Cite this