License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.81
URN: urn:nbn:de:0030-drops-156770
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15677/
Goyal, Vipul ;
Raizes, Justin ;
Soni, Pratik
Time-Traveling Simulators Using Blockchains and Their Applications
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.
BibTeX - Entry
@InProceedings{goyal_et_al:LIPIcs.ITCS.2022.81,
author = {Goyal, Vipul and Raizes, Justin and Soni, Pratik},
title = {{Time-Traveling Simulators Using Blockchains and Their Applications}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {81:1--81:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15677},
URN = {urn:nbn:de:0030-drops-156770},
doi = {10.4230/LIPIcs.ITCS.2022.81},
annote = {Keywords: Cryptography, Zero Knowledge, Secure Two-Party Computation, Blockchain}
}
|
Keywords: |
|
Cryptography, Zero Knowledge, Secure Two-Party Computation, Blockchain |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
