Paper 2002/054

SiBIR: Signer-Base Intrusion-Resilient Signatures

Gene Itkis and Leonid Reyzin

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.