TY - JOUR

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

AU - Howgrave-Graham, Nick A.

AU - Nguyen, Phong Q.

AU - Shparlinski, Igor E.

PY - 2003/7

Y1 - 2003/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0038129638&partnerID=8YFLogxK

U2 - 10.1090/S0025-5718-03-01495-9

DO - 10.1090/S0025-5718-03-01495-9

M3 - Article

VL - 72

SP - 1473

EP - 1485

JO - Mathematics of Computation

JF - Mathematics of Computation

SN - 0025-5718

IS - 243

ER -