### On the Impossibility of Probabilistic Proofs in Relativized Worlds

Alessandro Chiesa and Siqi Liu

##### Abstract

We initiate the systematic study of probabilistic proofs in relativized worlds. The goal is to understand, for a given oracle, if there exist "non-trivial" probabilistic proofs for checking deterministic or nondeterministic computations that make queries to the oracle. This question is intimately related to a recent line of work that builds cryptographic primitives (e.g., hash functions) via constructions that are "friendly" to known probabilistic proofs. This improves the efficiency of probabilistic proofs for computations calling these primitives. We prove that "non-trivial" probabilistic proofs relative to several natural oracles do not exist. Our results provide strong complexity-theoretic evidence that certain functionalities cannot be treated as black boxes, and thus investing effort to instantiate these functionalities via constructions tailored to known probabilistic proofs may be inherent.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. MAJOR revision.ITCS 2020
Keywords
probabilistically checkable proofsrelativization
Contact author(s)
alexch @ berkeley edu
History
Short URL
https://ia.cr/2019/1430

CC BY

BibTeX

@misc{cryptoeprint:2019/1430,
author = {Alessandro Chiesa and Siqi Liu},
title = {On the Impossibility of Probabilistic Proofs in Relativized Worlds},
howpublished = {Cryptology ePrint Archive, Paper 2019/1430},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/1430}},
url = {https://eprint.iacr.org/2019/1430}
}

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