Hidden number problem with the trace and bit security of XTR and LUC

Wen Ching W. Li, Mats Näslund, Igor E. Shparlinski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations


We consider a certain generalization of the hidden number problem introduced by Boneh and Venkatesan in 1996. Considering the XTR variation of Diffie-Hellman, we apply our results to show security of the log1/2 p most significant bits of the secret, in analogy to the results known for the classical Diffie-Hellman scheme. Our method is based on bounds of exponential sums which were introduced by Deligne in 1977. We proceed to show that the results are also applicable to the LUC scheme. Here, assuming the LUC function is one-way, we can in addition show that each single bit of the argument is a hard-core bit.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2002 - 22nd Annual International Cryptology Conference, Proceedings
EditorsMoti Yung
PublisherSpringer Verlag
Number of pages16
ISBN (Electronic)354044050X, 9783540440505
StatePublished - 2002
Event22nd Annual International Cryptology Conference, CRYPTO 2002 - Santa Barbara, United States
Duration: Aug 18 2002Aug 22 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other22nd Annual International Cryptology Conference, CRYPTO 2002
Country/TerritoryUnited States
CitySanta Barbara

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Hidden number problem with the trace and bit security of XTR and LUC'. Together they form a unique fingerprint.

Cite this