International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: SiBIR: Signer-Base Intrusion-Resilient Signatures

Gene Itkis
Leonid Reyzin
Search ePrint
Search Google
Abstract: 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.
  title={SiBIR: Signer-Base Intrusion-Resilient Signatures},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / intrusion resilience, forward security, digital signatures, Guillous-Quisquater, certificates, revocation},
  note={Crypto 2002 11865 received 30 Apr 2002, last revised 27 Jun 2002},
  author={Gene Itkis and Leonid Reyzin},