CryptoDB
Hardness Along the Boundary: Towards One-Way Functions from the Worst-case Hardness of Time-Bounded Kolmogorov Complexity
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | We consider the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, ${\sf MINK^{poly}}$---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 standard derandomization assumptions, worst-case hardness of the \emph{boundary} version of this classic problem characterizes OWFs. In more detail, let ${\sf boundry-MINK^{t_1, t_2}}$ 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 ${\sf boundry-MINK^{poly}} \notin \ioBPP$ if ${\sf boundry-MINK^{t_1, t_2}} \notin \ioBPP$ for all polynomials $t_1,t_2$. Our main result shows that under standard derandomization assumptions, OWF exist iff ${\sf boundry-MINK^{poly}} \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. |
BibTeX
@inproceedings{crypto-2025-35753,
title={Hardness Along the Boundary: Towards One-Way Functions from the Worst-case Hardness of Time-Bounded Kolmogorov Complexity},
publisher={Springer-Verlag},
author={Yanyi Liu and Rafael Pass},
year=2025
}