Paper 2019/644

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

Aydin Abadi, Michele Ciampi, Aggelos Kiayias, and Vassilis Zikas


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. Nevertheless, to our knowledge, there are no recent blockchain-based proposals that are formally proved in a composable 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 refer to the corresponding primitives as timed to indicate this association. We propose timed versions of primitives commonly used for authenticating information, such as digital signatures, non-interactive zero-knowledge proofs, and signatures of knowledge and show how those can be UC-securely implemented by a protocol that makes ideal (blackbox) access to a global transaction ledger based on the ledger proposed by Badertscher et al. [CRYPTO 2017] which is UC realized by the Bitcoin backbone protocol [Eurocrypt 2015]. 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 implement UC-securely assuming the ledger functionality. Given the many potential uses of such a beacon in cryptographic protocols this result may be of independent interest.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
BlockchainDigital SignaturesZero-knowledge ProofsSignatures of KnowledgeUniversal Composability
Contact author(s)
aydin abadi @ ed ac uk
mciampi @ ed ac uk
akiayias @ inf ed ac uk
vassilis zikas @ ed ac uk
2019-06-04: received
Short URL
Creative Commons Attribution


      author = {Aydin Abadi and Michele Ciampi and Aggelos Kiayias and Vassilis Zikas},
      title = {Timed Signatures and Zero-Knowledge Proofs -Timestamping in the Blockchain Era-},
      howpublished = {Cryptology ePrint Archive, Paper 2019/644},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.