Credit: Getty Images
Let Kt(x) denote the Levin-Kolmogorov Complexity of the string x, and let MKtP denote the language of pairs (x, k) having the property that Kt(x) ≤ k. We demonstrate that:
Taken together, these results show that the only "gap" toward getting (infinitely-often) OWFs from the assumption that EXP ≠ BPP is the seemingly "minor" technical gap between two-sided error and errorless average-case hardness of the MKtP problem.
A one-way function6 (OWF) is a function f that can be efficiently computed (in polynomial time), yet no probabilistic polynomial-time (PPT) algorithm can invert f with inverse polynomial probability for infinitely many input lengths n. Whether one-way functions exist is unequivocally the most important open problem in cryptography (and arguably the most important open problem in the theory of computation, see e.g., Levin19): OWFs are both necessary12 and sufficient for many of the most central cryptographic primitives and protocols (e.g., pseudorandom generators,2, 11 pseudo-random functions,7 private-key encryption,8 etc.)
While many candidate constructions of OWFs are known, the question of whether OWFs can be based on some "standard" complexity-theoretic assumption is mostly wide open.
No entries found