2014 | OriginalPaper | Buchkapitel
Leakage-Resilient Signatures with Graceful Degradation
verfasst von : Jesper Buus Nielsen, Daniele Venturi, Angela Zottarel
Erschienen in: Public-Key Cryptography – PKC 2014
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
,
σ
) even after receiving some
λ
bits of leakage on the signing key. If ∣
σ
∣ ≤
λ
, then the adversary can just choose to leak a valid signature
σ
, 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
,
σ
1
), …, (
m
n
,
σ
n
) after receiving
λ
bits of leakage. If
λ
= 0, this is the usual notion of existential unforgeability. If 1 <
λ
< ∣
σ
∣, this is essentially the usual notion of existential unforgeability in the presence of leakage. In addition, for
λ
≥ ∣
σ
∣ 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.