**Leakage-Resilient Signatures with Graceful Degradation**

*Jesper Buus Nielsen and Daniele Venturi and Angela Zottarel*

**Abstract: **We investigate new models and constructions which allow
leakage-resilient signatures secure against existential forgeries,
where the signature is much shorter than the leakage bound.
Current models of leakage-resilient signatures against existential
forgeries demand that the adversary cannot produce a new valid
message/signature pair $(m, \sigma)$ even after receiving some
$\lambda$ bits of leakage on the signing key. If $\vert \sigma \vert
\le \lambda$, then the adversary can just choose to leak a valid
signature $\sigma$, and hence signatures must be larger than the
allowed leakage, which is impractical as the goal often is to have
large signing keys to allow a lot of leakage.

We propose a new notion of leakage-resilient signatures against existential forgeries where we demand that the adversary cannot produce $n = \lfloor \lambda / \vert \sigma \vert \rfloor + 1$ distinct valid message/signature pairs $(m_1, \sigma_1), \ldots, (m_n, \sigma_n)$ after receiving $\lambda$ bits of leakage. If $\lambda = 0$, this is the usual notion of existential unforgeability. If $1 < \lambda < \vert \sigma \vert$, this is essentially the usual notion of existential unforgeability in the presence of leakage. In addition, for $\lambda \ge \vert \sigma \vert$ our new notion still guarantees the best possible, namely that the adversary cannot produce more forgeries than he could have leaked, hence graceful degradation.

Besides the game-based notion hinted above, we also consider a variant which is more simulation-based, in that it asks that from the leakage a simulator can ``extract'' a set of $n-1$ messages (to be thought of as the messages corresponding to the leaked signatures), and no adversary can produce forgeries not in this small set. The game-based notion is easier to prove for a concrete instantiation of a signature scheme. The simulation-based notion is easier to use, when leakage-resilient signatures are used as components in larger protocols.

We prove that the two notion are equivalent and present a generic construction of signature schemes meeting our new notion and a concrete instantiation under fairly standard assumptions. We further give an application, to leakage-resilient identification.

**Category / Keywords: **public-key cryptography / leakage resilience

**Original Publication**** (with minor differences): **IACR-PKC-2014

**Date: **received 7 Jul 2014

**Contact author: **jbn at cs au dk

**Available format(s): **PDF | BibTeX Citation

**Version: **20140708:063837 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]