Welcome to the resource topic for 2021/513
Title:
On One-way Functions from NP-Complete Problems
Authors: Yanyi Liu, Rafael Pass
Abstract:We present the first natural \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 \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 $t(n)\geq n^2$, there exists some polynomial $\zeta$ such that $\mcktp[\zeta]$ is $\NP$-complete. We additionally extend the result of Liu-Pass (FOCS'20) to show that for every polynomial $t(n)\geq 1.1n$, and every polynomial $\zeta(\cdot)$, mild average-case hardness of $\mcktp[\zeta]$ is equivalent to the existence of OWFs. Taken together, these results provide the following crisp characterization of what is required to base OWFs on $\NP \not \subseteq \BPP$: \emph{There exists concrete polynomials $t,\zeta$ such that Basing OWFs on \NP \not \subseteq \BPP‘’ is equivalent to providing a worst-case to (mild) average-case reduction for $\mcktp[\zeta]$''.} In other words, the holy-grail’’ of Cryptography (i.e., basing OWFs on \NP \not\subseteq \BPP) is equivalent to a basic question in algorithmic information theory. As an independent contribution, we show that our \NP-completeness result can be used to shed new light on the feasibility of the \emph{polynomial-time bounded symmetry of information} assertion (Kolmogorov’68).
ePrint: https://eprint.iacr.org/2021/513
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .