You are looking at a specific version 20190626:064205 of this paper. See the latest version.

Paper 2019/754

A Round-Collapse Theorem for Computationally-Sound Protocols; or, TFNP is Hard (on Average) in Pessiland

Rafael Pass and Muthuramakrishnan Venkitasubramaniam

Abstract

Consider the following two fundamental open problems in complexity theory: 1) Does a hard-on-average language in $\mathsf{NP}$ imply the existence of one-way functions? 2) Does a hard-on-average language in $\mathsf{NP}$ imply a hard problem in $\mathsf{TFNP}$ (i.e., the class of \emph{total} $\mathsf{NP}$ search problem)? We show that the answer to (at least) one of these questions is yes. In other words, in Impagliazzo's Pessiland (where $\mathsf{NP}$ is hard-on-average, but one-way functions do not exist), $\mathsf{TFNP}$ is unconditionally hard (on average). This result follows from a more general theory of interactive average-case complexity, and in particular, a novel round-collapse theorem for computationally-sound protocols, analogous to Babai-Moran's celebrated round-collapse theorem for information-theoretically sound protocols. As another consequence of this treatment, we show that the existence of $O(1)$-round public-coin non-trivial arguments (i.e., argument systems that are not proofs) imply the existence of a hard-on-average problem in $\mathsf{NP}/\mathsf{poly}$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
TFNPround-collapseaverage-case hardness
Contact author(s)
muthuv @ cs rochester edu
History
2020-04-15: last of 2 revisions
2019-06-26: received
See all versions
Short URL
https://ia.cr/2019/754
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.