On Building Fine-Grained One-Way Functions from Strong Average-Case Hardness

Abstract Constructing one-way functions from average-case hardness is a long-standing open problem. A positive result would exclude Pessiland (Impagliazzo ’95) and establish a highly desirable win–win situation: either (symmetric) cryptography exists unconditionally, or all $$\textsf{NP} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> problems can be solved efficiently on the average. Motivated by the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate win–win results of the following type: either there are fine-grained one-way functions (FGOWF), or non-trivial speedups can be obtained for all $$\textsf{NP} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> problems on the average. FGOWFs only require a fixed polynomial gap (as opposed to superpolynomial) between the running time of the function and the running time of an inverter. We obtain three main results: Construction. We show that if there is an $$\textsf{NP} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> language having a very strong form of average-case hardness, which we call block finding hardness , then FGOWF exist. We provide heuristic support for this very strong average-case hardness notion by showing that it holds for a random language. Then, we study whether weaker (and more natural) forms of average-case hardness could already suffice to obtain FGOWF and obtain two negative results: Separation I. We provide a strong oracle separation for the implication ( $$\exists $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>∃</mml:mo> </mml:math> exponentially average-case hard $$\textsf{NP} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> language $$\implies $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>⇒</mml:mo> </mml:math> $$\exists $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>∃</mml:mo> </mml:math> FGOWF). Separation II. We provide a second strong negative result for an even weaker candidate win–win result. Namely, we rule out a relativizing proof for the implication ( $$\exists $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>∃</mml:mo> </mml:math> exponentially average-case $$\textsf{NP} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>NP</mml:mi> </mml:math> hard language whose hardness amplifies optimally through parallel repetitions $$\implies $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>⇒</mml:mo> </mml:math> $$\exists $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>∃</mml:mo> </mml:math> FGOWF). This separation forms the core technical contribution of our work.