A nonuniform algorithm for the hidden number problem in subgroups

Igor E. Shparlinski, Arne Winterhof

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


Boneh and Venkatesan have proposed a polynomial time algorithm in a non-uniform model for recovering a "hidden" element α ∈ Fp, where p is prime, from very short strings of the most significant bits of the residue of αt modulo p for several randomly chosen t ∈ Fp. Here we modify the scheme and amplify the uniformity of distribution of the 'multipliers' t and thus extend this result to subgroups of Fp*, which are more relevant to practical usage. As in the work of Boneh and Venkatesan, our result can be applied to the bit security of Diffie-Hellman related encryption schemes starting with subgroups of very small size, including all cryptographically interesting subgroups.

Original languageEnglish
Pages (from-to)416-424
Number of pages9
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publication statusPublished - 2004


  • Diffie-Hellman key exchange
  • Exponential sums
  • Hidden number problem
  • Lattice reduction
  • Nonuniform algorithm
  • Waring problem in finite fields


Dive into the research topics of 'A nonuniform algorithm for the hidden number problem in subgroups'. Together they form a unique fingerprint.

Cite this