Date Added: Jan 2012
In the auxiliary input model an adversary is allowed to see a computationally hard-to-invert function of the secret key. The auxiliary input model weakens the bounded leakage assumption commonly made in leakage resilient cryptography as the hard-to-invert function may information-theoretically reveal the entire secret key. In this paper, the authors propose the first constructions of digital signature schemes that are secure in the auxiliary input model. Their main contribution is a digital signature scheme that is secure against chosen message attacks when given an exponentially hard-to-invert function of the secret key. As a second contribution, they construct a signature scheme that achieves security for random messages assuming that the adversary is given a polynomial-time hard to invert function.