Title: Pseudo-deterministic Proofs,
Abstract: We introduce pseudo-deterministic interactive proofs (psdAM): 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 pseudo-deterministic interactive proofs as an extension of the study
of pseudo-deterministic 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 pseudo-determinism 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.