You are looking at a specific version 20210430:222411 of this paper. See the latest version.

Paper 2021/513

On One-way Functions from NP-Complete Problems

Yanyi Liu and Rafael Pass

Abstract

We present the first natural NP-complete problem whose average-case hardness w.r.t. the uniform distribution over instances is equivalent to the existence of one-way functions (OWFs). The problem, which originated in the 1960s, is the Conditional Time-Bounded Kolmogorov Complexity Problem: let $K^t(x | 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$[t,\zeta]$ be the set of strings $(x,z,k)$ where $|z| = \zeta(|x|)$, $|k| = \log |x|$ and $K^t(x | z)< k$, where, for our purposes, a ``program'' is defined as a RAM machine. Our main results shows that for every polynomial $t(n)\geq n^2$, there exists some polynomial $\zeta$ such that McKTP$[t,\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$[t,\zeta]$ is equivalent to the existence of OWFs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. On https://eccc.weizmann.ac.il/
Keywords
one-way functionsKolmogorov complexityaverage-case complexity
Contact author(s)
yl2866 @ cornell edu,rafael @ cs cornell edu
History
2021-11-28: last of 2 revisions
2021-04-23: received
See all versions
Short URL
https://ia.cr/2021/513
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.