Time capsule signature

We introduce a new cryptographic problem called time capsule signature. Time capsule signature is a 'future signature' that becomes valid from a specific future time t, when a trusted third party (called Time Server) publishes some trapdoor information associated with the time t. In addition, time capsule signature should satisfy the following properties: (1) If the signer wants, she can make her time capsule signature effective before the pre-defined time t. (2) The recipient of 'future signature' can verify right away that the signature will become valid no later than at time t. (3) Time Server need not contact any user at any time, and in fact does not need to know anything about the PKI employed by the users. (4) Signatures completed by the signer before time t are indistinguishable from the ones completed using the Time Server at time t. We provide the rigorous definition of time capsule signature and the generic construction based on another new primitive of independent interest, which we call identity-based trapdoor hard-to-invert relation (IDTHIR). We also show an efficient construction of ID-THIRs (and, hence, time capsule signatures) in the random oracle model, and a less efficient construction in the standard model. If the time t is replaced by a specific event, the concept of time capsule signature can be generalized to event capsule signature.