ECCC-Report TR24-136https://eccc.weizmann.ac.il/report/2024/136Comments and Revisions published for TR24-136en-usSun, 08 Sep 2024 14:15:35 +0300
Paper TR24-136
| One-Way Functions and pKt Complexity |
Shuichi Hirahara,
Zhenjian Lu,
Igor Oliveira
https://eccc.weizmann.ac.il/report/2024/136We introduce $\mathrm{pKt}$ complexity, a new notion of time-bounded Kolmogorov complexity that can be seen as a probabilistic analogue of Levin's $\mathrm{Kt}$ complexity. Using $\mathrm{pKt}$ complexity, we upgrade two recent frameworks that characterize one-way functions ($\mathrm{OWFs}$) via symmetry of information and meta-complexity, respectively. Among other contributions, we establish the following results:
- $\mathrm{OWFs}$ can be based on the worst-case assumption that $\mathrm{BPEXP}$ is not contained infinitely often in $\mathrm{P}/\mathrm{poly}$ if the failure of symmetry of information for $\mathrm{pKt}$ in the worst-case implies its failure on average.
- (Infinitely-often) $\mathrm{OWFs}$ exist if and only if the average-case easiness of approximating $\mathrm{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) $\mathrm{OWFs}$ on the assumption that $\mathrm{EXP} \not\subseteq \mathrm{BPP}$ if and only if there is a reduction from computing $\mathrm{Kt}$ on average with zero error to computing $\mathrm{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 $\mathrm{pKt}$ is both necessary and sufficient to unconditionally establish the existence of $\mathrm{OWFs}$.Sun, 08 Sep 2024 14:15:35 +0300https://eccc.weizmann.ac.il/report/2024/136