Cryptology ePrint Archive: Report 2019/644

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

Aydin Abadi and Michele Ciampi and Aggelos Kiayias and Vassilis Zikas

Abstract: 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.

Category / Keywords: cryptographic protocols / Blockchain, Digital Signatures, Zero-knowledge Proofs, Signatures of Knowledge, Universal Composability

Date: received 3 Jun 2019

Contact author: aydin abadi at ed ac uk,mciampi@ed ac uk,akiayias@inf ed ac uk,vassilis zikas@ed ac uk

Available format(s): PDF | BibTeX Citation

Version: 20190604:070346 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]