Mind your coins: fully leakage-resilient signatures with graceful degradation

We construct a new leakage-resilient signature scheme. Our scheme remains unforgeable in the noisy leakage model, where the only restriction on the leakage is that it does not decrease the min-entropy of the secret key by too much. The leakage information can depend on the entire state of the signer; this property is sometimes known as fully leakage resilience. An additional feature of our construction, is that it offers a graceful degradation of security in situations where standard existential unforgeability is impossible. This property was recently put forward by Nielsen et al. (PKC 2014) in the bounded leakage model, to deal with settings in which the secret key is much larger than the size of a signature. For security parameter κ , our scheme tolerates leakage on the entire state of the signer until ω(logκ) bits of min-entropy are left in the secret key, and is proven secure in the standard model. While we describe our scheme in terms of generic building blocks, we also explain how to instantiate it efficiently under fairly standard number-theoretic assumptions.