# [Resource Topic] 2014/529: Leakage-Resilient Signatures with Graceful Degradation

Welcome to the resource topic for 2014/529

Title:
Leakage-Resilient Signatures with Graceful Degradation

Authors: Jesper Buus Nielsen, Daniele Venturi, 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.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .