Cryptology ePrint Archive: Report 2010/522

Signatures Resilient to Continual Leakage on Memory and Computation

Tal Malkin and Isamu Teranishiy and Yevgeniy Vahlis and Moti Yung

Abstract: Recent breakthrough results by Brakerski et al and Dodis et al have shown that signature schemes can be made secure even if the adversary continually obtains information leakage from the secret key of the scheme. However, the schemes currently do not allow leakage on the secret key and randomness during signing, except in the random oracle model. Further, the random oracle based schemes require updates to the secret key in order to maintain security, even when no leakage during computation is present. We present the first signature scheme that is resilient to full continual leakage: memory leakage as well as leakage from processing during signing (both from the secret key and the randomness), in keygeneration, and in update. Our scheme can tolerate leakage of a 1 - o(1) fraction of the secret key between updates, and is proven secure in the standard model based on the symmetric external DDH (SXDH) assumption in bilinear groups. The time periods between updates are a function of the amount of leakage in the period (and nothing more). Our construction makes new use of the Groth-Sahai proof systems, and in particular avoids composing proofs, which gives improved efficiency. In addition, we introduce a new tool: independent pre-image resistant hash functions, which may be of independent interest.

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

Date: received 9 Oct 2010, last revised 9 Oct 2010

Contact author: teranisi at ah jp nec com

Available format(s): PDF | BibTeX Citation

Version: 20101012:131606 (All versions of this report)

Short URL: ia.cr/2010/522

Discussion forum: Show discussion | Start new discussion