Leakage resilient signatures Conference Paper

Author(s): Faust, Sebastian; Kiltz, Eike; Pietrzak, Krzysztof; Rothblum, Guy N
Title: Leakage resilient signatures
Title Series: LNCS
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. 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 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. Signature schemes that remain secure even if a bounded total amount of information is leaked were recently constructed, hence instantiating our construction with these schemes gives the first constructions of provably secure leakage-resilient signature schemes. The above construction assumes that the signing algorithm can sample truly random bits, and thus an implementation would need some special hardware (randomness gates). Simply generating this randomness using a leakage-resilient stream-cipher will in general not work. Our second contribution is a sound general principle to replace uniform random bits in any leakage-resilient construction with pseudorandom ones: run two leakage-resilient stream-ciphers (with independent keys) in parallel and then apply a two-source extractor to their outputs.
Keywords: Provably secure; Signature Scheme; Amount of information; Pseudo random; Side channel attack; Arbitrary information; Chosen message attacks; Digital signature schemes; First constructions; Internal state; Random bits; Security notion; Signature generation; Signing algorithm; Source extractor; Special hardware; Tree-based; Unforgeability
Conference Title: TCC: Theory of Cryptography Conference
Volume: 5978
Conference Dates: February 9-11, 2010
Conference Location: Zurich, Switzerland
Publisher: Springer  
Date Published: 2010-03-26
Start Page: 343
End Page: 360
Copyright Statement: © 2010 Springer
DOI: 10.1007/978-3-642-11799-2_21
Open access: no
IST Austria Authors
Related IST Austria Work