### Time-Traveling Simulators Using Blockchains and Their Applications

Vipul Goyal, Justin Raizes, and Pratik Soni

##### Abstract

Blockchain technology has the potential of transforming cryptography. We study the problem of round-complexity of zero-knowledge, and more broadly, of secure computation in the blockchain-hybrid model, where all parties can access the blockchain as an oracle. We study zero-knowledge and secure computation through the lens of a new security notion where the simulator is given the ability to time-travel” or more accurately, to look into the future states of the blockchain and use this information to perform simulation. Such a time-traveling simulator gives a novel security guarantee of the following form: whatever the adversary could have learnt from an interaction, it could have computed on its own shortly into the future (e.g., a few hours from now). We exhibit the power of time-traveling simulators by constructing round-efficient protocols in the blockchain-hybrid model. In particular, we construct: 1. Three-round zero-knowledge (ZK) argument for NP with a polynomial-time black-box time-traveling simulator. 2. Three-round secure two-party computation (2PC) for any functionality with a polynomial-time black-box time-traveling simulator for both parties. In addition to standard cryptographic assumptions, we rely on natural hardness assumptions for Proof-of-Work based blockchains. In comparison, in the plain model, three-round protocols with black-box simulation are impossible, and constructions with non-black-box simulation for ZK require novel cryptographic assumptions while no construction for three-round 2PC is known. Our three-round 2PC result relies on a new, two-round extractable commitment that admits a time-traveling extractor.

Note: A preliminary version of this paper appears at ITCS 2022.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. MAJOR revision.ITCS 2022
Keywords
Zero-knowledgeSecure two-party computationBlockchains
Contact author(s)
psoni @ andrew cmu edu
jraizes @ andrew cmu edu
vipul @ cmu edu
History
Short URL
https://ia.cr/2022/035

CC BY

BibTeX

@misc{cryptoeprint:2022/035,
author = {Vipul Goyal and Justin Raizes and Pratik Soni},
title = {Time-Traveling Simulators Using Blockchains and Their Applications},
howpublished = {Cryptology ePrint Archive, Paper 2022/035},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/035}},
url = {https://eprint.iacr.org/2022/035}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.