About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Mathematics of Computation
Paper
Hidden number problem with hidden multipliers, timed-release crypto, and noisy exponentiation
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.