Paper 2023/1086
On Oneway Functions and the Worstcase Hardness of TimeBounded Kolmogorov Complexity
Abstract
Whether oneway functions (OWF) exist is arguably the most important problem in Cryptography, and beyond. While lots of candidate constructions of oneway functions are known, and recently also problems whose averagecase hardness characterize the existence of OWFs have been demonstrated, the question of whether there exists some \emph{worstcase hard problem} that characterizes the existence of oneway functions has remained open since their introduction in 1976. In this work, we present the first ``OWFcomplete'' promise problema promise problem whose worstcase hardness w.r.t. $\BPP$ (resp. $\Ppoly$) is \emph{equivalent} to the existence of OWFs secure against $\PPT$ (resp. $\nuPPT$) algorithms. The problem is a variant of the Minimum Timebounded Kolmogorov Complexity problem ($\mktp[s]$ with a threshold $s$), where we condition on instances having small ``computational depth''. We furthermore show that depending on the choice of the threshold $s$, this problem characterizes either ``standard'' (polynomiallyhard) OWFs, or quasi polynomially or subexponentiallyhard OWFs. Additionally, when the threshold is sufficiently small (e.g., $2^{O(\sqrt{n})}$ or $\poly\log n$) then \emph{sublinear} hardness of this problem suffices to characterize quasipolynomial/subexponential OWFs. While our constructions are blackbox, our analysis is \emph{non black box}; we additionally demonstrate that fully blackbox constructions of OWF from the worstcase hardness of this problem are impossible. We finally show that, under Rudich's conjecture, and standard derandomization assumptions, our problem is not inside $\coAM$; as such, it yields the first candidate problem believed to be outside of $\AM \cap \coAM$, or even ${\bf SZK}$, whose worst case hardness implies the existence of OWFs.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 Oneway functionsKolmogorov complexityWorstcase assumptions
 Contact author(s)

yl2866 @ cornell edu
rafaelp @ tau ac il  History
 20230905: revised
 20230712: received
 See all versions
 Short URL
 https://ia.cr/2023/1086
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1086, author = {Yanyi Liu and Rafael Pass}, title = {On Oneway Functions and the Worstcase Hardness of TimeBounded Kolmogorov Complexity}, howpublished = {Cryptology ePrint Archive, Paper 2023/1086}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1086}}, url = {https://eprint.iacr.org/2023/1086} }