Welcome to the resource topic for 2024/1388
Title:
OneWay Functions and pKt Complexity
Authors: Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
Abstract:We introduce \mathsf{pKt} complexity, a new notion of timebounded 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 oneway functions (\mathsf{OWF}) via symmetry of information and metacomplexity, respectively. Among other contributions, we establish the following results:

\mathsf{OWF} can be based on the worstcase 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{worstcase} implies its failure on \textit{average}.

\mathsf{OWF} exist if and only if the averagecase easiness of approximating \mathsf{pKt} with \textit{twosided} error implies its (mild) averagecase easiness with \textit{onesided} error.
Previously, in a celebrated result, Liu and Pass (CRYPTO 2021 and CACM 2023) proved that one can base (infinitelyoften) \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{twosided} error. In contrast, our second result shows that closing the gap between twosided error and onesided error averagecase 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 .