Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation

Nick A. Howgrave-Graham*, Phong Q. Nguyen, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

We consider a generalisation of the hidden number problem recently introduced by Boneh and Venkatesan. The initial problem can be stated as follows: recover a number a ∈ double-struck F signp such that for many known random t ∈ double-struck F signp approximations to the values of ⌊at⌋p are known. Here we study a version of the problem where the "multipliers" t are not known but rather certain approximations to them are given. We present a probabilistic polynomial time solution when the error is small enough, and we show that the problem cannot be solved if the error is sufficiently large. We apply the result to the bit security of "timed-release crypto" introduced by Rivest, Shamir and Wagner, to noisy exponentiation black-boxes and to the bit security of the "inverse" exponentiation. We also show that it implies a certain bit security result for Weil Dairine on elliotic curves.

Original languageEnglish
Pages (from-to)1473-1485
Number of pages13
JournalMathematics of Computation
Volume72
Issue number243
DOIs
Publication statusPublished - Jul 2003

Fingerprint Dive into the research topics of 'Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation'. Together they form a unique fingerprint.

Cite this