Cryptology ePrint Archive: Report 2009/282

Leakage-Resilient Signatures

Sebastian Faust and Eike Kiltz and Krzysztof Pietrzak and Guy Rothblum

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.

Category / Keywords: public-key cryptography / signatures, leakage-resilience

Date: received 12 Jun 2009

Contact author: sebastian faust at esat kuleuven be

Available formats: PDF | BibTeX Citation

Version: 20090616:201420 (All versions of this report)

Discussion forum: Show discussion | Start new discussion