One of the main challenges in constructing fully leakage-resilient signature schemes is dealing with leakage that may depend on the random bits used by the signing algorithm, and constructions of such schemes are known only in the random-oracle model. Moreover, even in the random-oracle model, known schemes are only resilient to leakage of less than half the length of their signing key.
In this paper we construct the first fully leakage-resilient signature schemes without random oracles. We present a scheme that is resilient to any leakage of length $(1-o(1))L$ bits, where $L$ is the length of the signing key. Our approach relies on generic cryptographic primitives, and at the same time admits rather efficient instantiations based on specific number-theoretic assumptions. In addition, we show that our approach extends to the continual-leakage model, recently introduced by Dodis, Haralambiev, Lopez-Alt and Wichs (FOCS '10), and by Brakerski, Tauman Kalai, Katz and Vaikuntanathan (FOCS '10). In this model the signing key is allowed to be refreshed, while its corresponding verification key remains fixed, and the amount of leakage is assumed to be bounded only in between any two successive key refreshes.
Category / Keywords: public-key cryptography / digital signatures, leakage resilience, public-key cryptography Publication Info: EUROCRYPT '11, Journal of Cryptology. Date: received 14 Sep 2010, last revised 7 Oct 2012 Contact author: eboyle at mit edu Available format(s): PDF | BibTeX Citation Version: 20121008:023750 (All versions of this report) Discussion forum: Show discussion | Start new discussion