Paper 2021/513

On One-way Functions from NP-Complete Problems

Yanyi Liu and Rafael Pass

Abstract

We present the first natural $\text{NP}$-complete problem whose average-case hardness w.r.t. the uniform distribution over instances is \emph{equivalent} to the existence of one-way functions (OWFs). The problem, which originated in the 1960s, is the \emph{Conditional Time-Bounded Kolmogorov Complexity Problem}: let $K^t(x\mid z)$ be the length of the shortest ``program'' that, given the ``auxiliary input'' $z$, outputs the string $x$ within time $t(|x|)$, and let $\text{mcktp}[\zeta ]$ be the set of strings $(x,z,k)$ where $|z|=\zeta (|x|)$, $|k|=\log |x|$ and $K^t(x\mid z)<k$, where, for our purposes, a ``program'' is defined as a RAM machine. Our main result shows that for every polynomial $$, there exists some polynomial $$ such that $$ is $$-complete. We additionally extend the result of Liu-Pass (FOCS'20) to show that for every polynomial $$, and every polynomial $$, mild average-case hardness of $$ is equivalent to the existence of OWFs. Taken together, these results provide the following crisp characterization of what is required to base OWFs on $$: \emph{There exists concrete polynomials $$ such that ``Basing OWFs on $$'' is equivalent to providing a ``worst-case to (mild) average-case reduction for $$''.} In other words, the ``holy-grail'' of Cryptography (i.e., basing OWFs on $$) is equivalent to a basic question in algorithmic information theory. As an independent contribution, we show that our $$-completeness result can be used to shed new light on the feasibility of the \emph{polynomial-time bounded symmetry of information} assertion (Kolmogorov'68).