Welcome to the resource topic for 2024/1388
Title:
One-Way Functions and pKt Complexity
Authors: Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
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:
-
\mathsf{OWF} can be based on the worst-case assumption that \mathsf{BPEXP} is not contained infinitely often in \mathsf{P}/\mathsf{poly} if the failure of symmetry of information for \mathsf{pKt} in the \textit{worst-case} implies its failure on \textit{average}.
-
\mathsf{OWF} exist if and only if the average-case easiness of approximating \mathsf{pKt} with \textit{two-sided} error implies its (mild) average-case easiness with \textit{one-sided} error.
Previously, in a celebrated result, Liu and Pass (CRYPTO 2021 and CACM 2023) proved that one can base (infinitely-often) \mathsf{OWF} on the assumption that \mathsf{EXP} \nsubseteq \mathsf{BPP} if and only if there is a reduction from computing \mathsf{Kt} on average with \textit{zero} error to computing \mathsf{Kt} on average with \textit{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 \mathsf{pKt} is both necessary and sufficient to \textit{unconditionally} establish the existence of \mathsf{OWF}.
ePrint: https://eprint.iacr.org/2024/1388
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 .