Liu, Yanyi ;
Pass, Rafael
On OneWay Functions from NPComplete Problems
Abstract
We present the first natural NPcomplete problem whose averagecase hardness w.r.t. the uniform distribution over instances is equivalent to the existence of oneway functions (OWFs). The problem, which originated in the 1960s, is the Conditional TimeBounded 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 McK^tP[ζ] be the set of strings (x,z,k) where z = ζ(x), k = log x and K^t(x∣z) < k, where, for our purposes, a "program" is defined as a RAM machine.
Our main result shows that for every polynomial t(n) ≥ n², there exists some polynomial ζ such that McK^tP[ζ] is NPcomplete. We additionally extend the result of LiuPass (FOCS'20) to show that for every polynomial t(n) ≥ 1.1n, and every polynomial ζ(⋅), mild averagecase hardness of McK^tP[ζ] 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 ⊈ BPP:
There exists concrete polynomials t,ζ such that "Basing OWFs on NP ⊈ BPP" is equivalent to providing a "worstcase to (mild) averagecase reduction for McK^tP[ζ]".
In other words, the "holygrail" of Cryptography (i.e., basing OWFs on NP ⊈ BPP) is equivalent to a basic question in algorithmic information theory.
As an independent contribution, we show that our NPcompleteness result can be used to shed new light on the feasibility of the polynomialtime bounded symmetry of information assertion (Kolmogorov'68).
BibTeX  Entry
@InProceedings{liu_et_al:LIPIcs.CCC.2022.36,
author = {Liu, Yanyi and Pass, Rafael},
title = {{On OneWay Functions from NPComplete Problems}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {36:136:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16598},
URN = {urn:nbn:de:0030drops165981},
doi = {10.4230/LIPIcs.CCC.2022.36},
annote = {Keywords: Oneway Functions, NPCompleteness, Kolmogorov Complexity}
}
11.07.2022
Keywords: 

Oneway Functions, NPCompleteness, Kolmogorov Complexity 
Seminar: 

37th Computational Complexity Conference (CCC 2022)

Issue date: 

2022 
Date of publication: 

11.07.2022 