Cryptology ePrint Archive: Report 2009/133

Signature Schemes with Bounded Leakage Resilience

Jonathan Katz

Abstract: A leakage-resilient cryptosystem remains secure even if arbitrary information about the secret key (or possibly other internal state information) is leaked to an adversary. We demonstrate the first constructions of leakage-resilient signature schemes that remain secure as long as a bounded amount of information, depending on the length $n$ of the secret key, is leaked. We show efficient schemes in the random oracle model that handle leakage of up to $(1/2-\epsilon) n$ bits of information about the signer's entire internal state. In the standard model, we show an inefficient scheme that can handle leakage of up to $(1-\epsilon) n$ bits of information about the secret key, and a one-time signature scheme tolerating arbitrary leakage of $n^{1-\epsilon}$ bits.

Category / Keywords: public-key cryptography / memory attacks, signatures

Date: received 22 Mar 2009, withdrawn 29 Mar 2009

Contact author: jkatz at cs umd edu

Available format(s): (-- withdrawn --)

Version: 20090330:012437 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]