Paper 2021/513
On Oneway Functions from NPComplete Problems
Yanyi Liu and Rafael Pass
Abstract
We present the first natural $\NP$complete problem whose averagecase hardness w.r.t. the uniform distribution over instances is \emph{equivalent} to the existence of oneway functions (OWFs). The problem, which originated in the 1960s, is the \emph{Conditional TimeBounded 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 LiuPass (FOCS'20) to show that for every polynomial $t(n)\geq 1.1n$, and every polynomial $\zeta(\cdot)$, mild averagecase 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 ``worstcase to (mild) averagecase reduction for $\mcktp[\zeta]$''.} In other words, the ``holygrail'' 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{polynomialtime bounded symmetry of information} assertion (Kolmogorov'68).
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision. https://eccc.weizmann.ac.il/report/2021/059/
 Keywords
 oneway functionsKolmogorov complexityaveragecase complexity
 Contact author(s)

yl2866 @ cornell edu
rafael @ cs cornell edu  History
 20211128: last of 2 revisions
 20210423: received
 See all versions
 Short URL
 https://ia.cr/2021/513
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/513, author = {Yanyi Liu and Rafael Pass}, title = {On Oneway Functions from NPComplete Problems}, howpublished = {Cryptology ePrint Archive, Paper 2021/513}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/513}}, url = {https://eprint.iacr.org/2021/513} }