Paper 2020/1326

Towards Fine-Grained One-Way Functions from Strong Average-Case Hardness

Chris Brzuska and Geoffroy Couteau

Abstract

Constructing one-way function 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, enabling many of the important primitives which are used to secure our communications, or all NP problems can be solved efficiently on the average, which would be revolutionary for algorithmists and industrials. Motivated by the strong interest of establishing such win-win results and the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate win-win results. Specifically, we study the following type of win-win results: either there are fine-grained one-way functions (FGOWF), which relax the standard notion of a one-way function by requiring only a fixed polynomial gap (as opposed to superpolynomial) between the running time of the function and the running time of an inverter, or nontrivial speedups can be obtained for all NP problems on the average. We obtain three main results: – We introduce the Random Language Model (RLM), which captures idealized average-case hard languages, analogous to how the random oracle model captures idealized one-way functions. In the RLM, we rule out an idealized version of Pessiland, where ideally hard languages would exist yet even weak forms of cryptography would fail. Namely, we provide a construction of a FGOWF (with quadratic hardness gap) and prove its security in the RLM. – On the negative side, we prove a strong oracle separation: we show that there is no black-box proof that either FGOWF exist, or non-trivial speedup can be obtained for all NP languages on average (i.e., there is no exponentially average-case hard NP languages). – We provide a second strong negative result for an even weaker candidate win-win result: there is no black-box proof that either FGOWF exist, or non-trivial speedups can be obtained for all NP languages on average when amortizing over many instances (i.e., there is no exponentially average-case hard NP languages whose hardness amplifies optimally through parallel repetitions). This separation forms the core technical contribution of our work. Our results lay the foundations for a program towards building fine-grained one-way functions from strong forms of average-case hardness, following the template of constructions in the Random Language Model. We provide a preliminary investigation of this program, showing black-box barriers toward instantiating our idealized constructions from natural hardness properties.