Goldwasser, Shafi ;
Grossman, Ofer ;
Holden, Dhiraj
PseudoDeterministic Proofs
Abstract
We introduce pseudodeterministic interactive proofs (psdIP): interactive proof systems for search problems where the verifier is guaranteed with high probability to output the same output on different executions. As in the case with classical interactive proofs, the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover.
We view pseudodeterministic interactive proofs as an extension of the study of pseudodeterministic randomized polynomial time algorithms: the goal of the latter is to find canonical solutions to search problems whereas the goal of the former is to prove that a solution to a search problem is canonical to a probabilistic polynomial time verifier.
Alternatively, one may think of the powerful prover as aiding the probabilistic polynomial time verifier to find canonical solutions to search problems, with high probability over the randomness of the verifier. The challenge is that pseudodeterminism should hold not only with respect to the randomness, but also with respect to the prover: a malicious prover should not be able to cause the verifier to output a solution other than the unique canonical one.
The IP=PSPACE characterization implies that psdIP = IP. The challenge is to find constant round pseudodeterministic interactive proofs for hard search problems. We show a constant round pseudodeterministic interactive proof for the graph isomorphism problem: on any input pair of isomorphic graphs (G_0,G_1), there exist a unique isomorphism phi from G_0 to G_1 (although many isomorphism many exist) which will be output by the verifier with high probability, regardless of any dishonest prover strategy.
In contrast, we show that it is unlikely that psdIP proofs with constant rounds exist for NPcomplete problems by showing that if any NPcomplete problem has a constant round psdIP protocol, then the polynomial hierarchy collapses.
BibTeX  Entry
@InProceedings{goldwasser_et_al:LIPIcs:2018:8366,
author = {Shafi Goldwasser and Ofer Grossman and Dhiraj Holden},
title = {{PseudoDeterministic Proofs}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {17:117:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8366},
URN = {urn:nbn:de:0030drops83669},
doi = {10.4230/LIPIcs.ITCS.2018.17},
annote = {Keywords: PseudoDeterministic, Interactive Proofs}
}
12.01.2018
Keywords: 

PseudoDeterministic, Interactive Proofs 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Issue date: 

2018 
Date of publication: 

12.01.2018 