A nonuniform algorithm for the hidden number problem in subgroups

Igor E. Shparlinski, Arne Winterhof

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

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)
Volume2947
Publication statusPublished - 2004

Keywords

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

Fingerprint

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

Cite this