Paper 2014/529
LeakageResilient Signatures with Graceful Degradation
Jesper Buus Nielsen, Daniele Venturi, and Angela Zottarel
Abstract
We investigate new models and constructions which allow leakageresilient signatures secure against existential forgeries, where the signature is much shorter than the leakage bound. Current models of leakageresilient 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 leakageresilient 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 gamebased notion hinted above, we also consider a variant which is more simulationbased, in that it asks that from the leakage a simulator can ``extract'' a set of $n1$ 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 gamebased notion is easier to prove for a concrete instantiation of a signature scheme. The simulationbased notion is easier to use, when leakageresilient 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 leakageresilient identification.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A minor revision of an IACR publication in PKC 2014
 Keywords
 leakage resilience
 Contact author(s)
 jbn @ cs au dk
 History
 20140708: received
 Short URL
 https://ia.cr/2014/529
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/529, author = {Jesper Buus Nielsen and Daniele Venturi and Angela Zottarel}, title = {LeakageResilient Signatures with Graceful Degradation}, howpublished = {Cryptology ePrint Archive, Paper 2014/529}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/529}}, url = {https://eprint.iacr.org/2014/529} }