Paper 2002/054

SiBIR: Signer-Base Intrusion-Resilient Signatures

Gene Itkis and Leonid Reyzin


We propose a new notion of intrusion-resilient signature schemes, which generalizes and improves upon both forward-secure [And97,BM99] and key-insulated [DKXY02] signature schemes. Specifically, as in the prior notions, time is divided into predefined time periods (e.g., days); each signature includes the number of the time time period in which it was generated; while the public key remains the same, the secret keys evolve with time. Also, as in key-insulated schemes, the user has two modules, signer and home base: the signer generates signatures on his own, and the base is needed only to help update the signer's key from one period to the next. The main strength of intrusion-resilient schemes, as opposed to prior notions, is that they remain secure even after arbitrarily many compromises of both modules, as long as the compromises are not simultaneous. Moreover, even if the intruder does compromise both modules simultaneously, she will still be unable to generate any signatures for the previous time periods. We provide an efficient intrusion-resilient signature scheme, provably secure in the random oracle model based on the strong RSA assumption. We also discuss how such schemes can eliminate the need for certificate revocation in the case of on-line authentication.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Crypto 2002
intrusion resilienceforward securitydigital signaturesGuillous-Quisquatercertificatesrevocation
Contact author(s)
reyzin @ bu edu
2002-06-27: revised
2002-04-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gene Itkis and Leonid Reyzin},
      title = {SiBIR: Signer-Base Intrusion-Resilient Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2002/054},
      year = {2002},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.