Paper 2009/282 Original: eprint.iacr.org/2009/282 ↗

Leakage-Resilient Signatures

Abstract

The strongest standard security notion for digital signature schemes is unforgeability under chosen message attacks. In practice, however, this notion can be insufficient due to ``side-channel attacks'' which exploit leakage of information about the secret internal state of the scheme's hardware implementation. In this work we put forward the notion of ``leakage-resilient signatures,'' which strengthens the standard security notion by giving the adversary the additional power to learn a bounded amount of arbitrary information about the secret state that was accessed during every signature generation. This notion naturally implies security against all possible side-channel attacks as long as the amount of information leaked on each invocation is bounded and ``only computation leaks information.'' The main result of this paper is a construction which gives a (tree based, stateful) leakage-resilient signature scheme based on any 3-time signature scheme. The amount of information that our scheme can safely leak per signature generation is $1/3$ of the information the underlying 3-time signature scheme can leak in total. Based on recent works by Alwen, Dodis, Wichs and by Katz we give several efficient instantiations of 3-time signature schemes with the required security properties, hence yielding the first constructions of provably secure leakage-resilient signature schemes.