Abstract
The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one of the main research objectives in the context of TFNP is to search for efficient algorithms for its subclasses, and at the same time proving hardness results where efficient algorithms cannot exist.
Currently, no problem in TFNP is known to be hard under assumptions such as NP hardness, the existence of oneway functions, or even publickey cryptography. The only known hardness results are based on less general assumptions such as the existence of collisionresistant hash functions, oneway permutations less established cryptographic primitives (e.g. program obfuscation or functional encryption).
Several works explained this status by showing various barriers to proving hardness of TFNP. In particular, it has been shown that hardness of TFNP hardness cannot be based on worstcase NP hardness, unless NP=coNP. Therefore, we ask the following question: What is the weakest assumption sufficient for showing hardness in TFNP?
In this work, we answer this question and show that hardonaverage TFNP problems can be based on the weak assumption that there exists a hardonaverage language in NP. In particular, this includes the assumption of the existence of oneway functions. In terms of techniques, we show an interesting interplay between problems in TFNP, derandomization techniques, and zeroknowledge proofs.
BibTeX  Entry
@InProceedings{hubcek_et_al:LIPIcs:2017:8162,
author = {Pavel Hub{\'a}cek and Moni Naor and Eylon Yogev},
title = {{The Journey from NP to TFNP Hardness}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {60:160:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8162},
URN = {urn:nbn:de:0030drops81627},
doi = {10.4230/LIPIcs.ITCS.2017.60},
annote = {Keywords: TFNP, derandomization, oneway functions, averagecase hardness}
}
Keywords: 

TFNP, derandomization, oneway functions, averagecase hardness 
Collection: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017) 
Issue Date: 

2017 
Date of publication: 

28.11.2017 