Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR21-059 | 28th November 2021 10:40

On One-way Functions from NP-Complete Problems

RSS-Feed




Revision #2
Authors: Yanyi Liu, Rafael Pass
Accepted on: 28th November 2021 10:41
Downloads: 23
Keywords: 


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).


Revision #1 to TR21-059 | 1st May 2021 00:57

On One-way Functions from NP-Complete Problems





Revision #1
Authors: Yanyi Liu, Rafael Pass
Accepted on: 1st May 2021 00:57
Downloads: 220
Keywords: 


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.


Paper:

TR21-059 | 20th April 2021 00:31

On One-way Functions from NP-Complete Problems





TR21-059
Authors: Yanyi Liu, Rafael Pass
Publication: 25th April 2021 13:26
Downloads: 469
Keywords: 


Abstract:

We present the first natural $\NP$-complete problem whose average-case hardness w.r.t. the uniform distribution over instances implies the existence of one-way functions (OWF). In fact, we prove that the existence of OWFs is \emph{equivalent} to mild average-case hardness of this $\NP$-complete problem. 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[t,\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 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 observe that the result of Liu-Pass (FOCS'20) extends 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.



ISSN 1433-8092 | Imprint