2026-07-21T23:56:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15677 2024-03-06T10:55:55Z ddc:004 open_access

Time-Traveling Simulators Using Blockchains and Their Applications Goyal, Vipul Raizes, Justin Soni, Pratik Cryptography Zero Knowledge Secure Two-Party Computation Blockchain 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vipul Goyal and Justin Raizes and Pratik Soni 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.81 urn:nbn:de:0030-drops-156770 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.81 eng https://creativecommons.org/licenses/by/4.0/legalcode