Paper 2010/522

Signatures Resilient to Continual Leakage on Memory and Computation

Tal Malkin, Isamu Teranishiy, Yevgeniy Vahlis, and Moti Yung


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
digital signaturesleakage resiliencepublic-key cryptography
Contact author(s)
teranisi @ ah jp nec com
2010-10-12: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.