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: - $\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}$. - (Infinitely-often) $\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}$.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published by the IACR in TCC 2024
- Keywords
- one-way functionsKolmogorov complexityaverage-case complexitysymmetry of information
- Contact author(s)
-
s_hirahara @ nii ac jp
zhenjian lu @ warwick ac uk
igor oliveira @ warwick ac uk - History
- 2024-09-04: revised
- 2024-09-04: received
- See all versions
- Short URL
- https://ia.cr/2024/1388
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1388, author = {Shuichi Hirahara and Zhenjian Lu and Igor C. Oliveira}, title = {One-Way Functions and {pKt} Complexity}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1388}, year = {2024}, url = {https://eprint.iacr.org/2024/1388} }