###
SiBIR: Signer-Base Intrusion-Resilient Signatures

by 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.

This work appears in Advances in Cryptology -- Crypto 2002, Moti Yung,
editor, Lecture Notes in Computer Science 2442, Springer-Verlag. ©IACR 2002.