Welcome to the resource topic for 2025/1497
Title:
Hardness Along the Boundary: Towards One-Way Functions from the Worst-case Hardness of Time-Bounded Kolmogorov Complexity
Authors: Yanyi Liu, Rafael Pass
Abstract:We consider the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, \KpolyA—that is, determining whether a string is time-bounded Kolmogorov random (K^t-random) or not—suffices to imply the existence of one-way functions (OWF).
Roughly speaking, our main result shows that under a natural strengthening of standard-type derandomization assumptions, worst-case hardness of the \emph{boundary} version of this classic problem characterizes OWFs.
In more detail, let \bKtA denote the problem of, given an instance x, deciding whether (a) K^{t_2}(x)\geq n-1, or (b) K^{t_1}(x) < n-1 \emph{but} K^{t_2}> n - \log n; that is, deciding whether x is K^t-random, or just ``near" K^t-random. We say that \bKpolyA \notin \ioBPP if \bKpolyA \notin \ioBPP for all polynomials t_1,t_2.
We show that under a natural strengthening of standard derandomization assumptions (namely, there exists a constant \varepsilon > 0 such that \E \not\subseteq {\sf ioNTIME}[2^{kn}] \slash 2^{\varepsilon n} for every k \in \N), OWF exist iff \bKpolyA \notin \ioBPP. Along the way, we also demonstrate that if we consider the probabilistic version of Kolmogorov complexity (referred to as pK^t) instead, then the characterization holds unconditionally.
We finally observe that for most standard optimization problems, hardness along boundary" is equivalent to plain" worst-case hardness, indicating that assuming hardness along the boundary may be WLOG.
ePrint: https://eprint.iacr.org/2025/1497
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .