Paper 2010/522

Signatures Resilient to Continual Leakage on Memory and Computation

Tal Malkin, Isamu Teranishiy, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
digital signaturesleakage resiliencepublic-key cryptography
Contact author(s)
teranisi @ ah jp nec com
History
2010-10-12: received
Short URL
https://ia.cr/2010/522
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/522,
      author = {Tal Malkin and Isamu Teranishiy and Yevgeniy Vahlis and Moti Yung},
      title = {Signatures Resilient to Continual Leakage on Memory and Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2010/522},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/522}},
      url = {https://eprint.iacr.org/2010/522}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.