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