Digitally signed documents (e.g. contracts) would quickly lose their validity if the signing keys were revoked or the signature scheme was broken. The conventional validation techniques have been designed just for ephemeral use of signatures and are impractical for long-term validation. We present a new scheme that: (1)pro vides fast revocation while giving no extra power to on-line service providers; (2)supports long-term validation; (3)is lightweight and scalable. All authors were supported by the Estonian SF, grant no. 4150