Timed Signatures and Zero-Knowledge Proofs: Timestamping in the Blockchain Era

Timestamping is an important cryptographic primitive with numerous applications. The availability of a decentralized blockchain such as that offered by the Bitcoin protocol offers new possibilities to realise timestamping services. Even though there are blockchain-based timestamping proposals, they are not formally defined and proved in a universally composable (UC) setting. In this work, we put forth the first formal treatment of timestamping cryptographic primitives in the UC framework with respect to a global clock. We propose timed versions of primitives commonly used for authenticating information, such as digital signatures, non-interactive zero-knowledge proofs, and signatures of knowledge. We show how they can be UC-securely constructed by a protocol that makes ideal (blackbox) access to a transaction ledger. Our definitions introduce a fine-grained treatment of the different timestamping guarantees, namely security against postdating and backdating attacks; our results treat each of these cases separately and in combination, and shed light on the assumptions that they rely on. Our constructions rely on a relaxation of an ideal beacon functionality, which we construct UC-securely. Given many potential use cases of such a beacon in cryptographic protocols, this result is of independent interest.