Paper 2024/1388

One-Way Functions and pKt Complexity

Abstract

We introduce $\mathsf{pKt}$ complexity, a new notion of time-bounded Kolmogorov complexity that can be seen as a probabilistic analogue of Levin's $\mathsf{Kt}$ complexity. Using $\mathsf{pKt}$ complexity, we upgrade two recent frameworks that characterize one-way functions ($\mathsf{OWF}$) via symmetry of information and meta-complexity, respectively. Among other contributions, we establish the following results: - $$ can be based on the worst-case assumption that $$ is not contained infinitely often in $$ if the failure of symmetry of information for $$ in the $$ implies its failure on $$. - (Infinitely-often) $$ exist if and only if the average-case easiness of approximating $$ with $$ error implies its (mild) average-case easiness with $$ error. Previously, in a celebrated result, Liu and Pass (CRYPTO 2021 and CACM 2023) proved that one can base (infinitely-often) $$ on the assumption that $$ if and only if there is a reduction from computing $$ on average with $$ error to computing $$ on average with $$ error. In contrast, our second result shows that closing the gap between two-sided error and one-sided error average-case algorithms for approximating $$ is both necessary and sufficient to $$ establish the existence of $$.