International Association
for Cryptologic Research

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