2020/09/24 by Rafael Pass, Liu, Yanyi, Pass, Rafael · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2009.11514
openalex publication_date 2020/09/24 · openalex created_date 2020/10/01 · openalex updated_date 2026/07/28
We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n)≥ (1+ε)n, ε>0, the following are equivalent: - One-way functions exists (which in turn is equivalent to the existence of secure private-key encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more); - t-time bounded Kolmogorov Complexity, Kt, is mildly hard-on-average (i.e., there exists a polynomial p(n)>0 such that no PPT algorithm can compute Kt, for more than a 1-(1)/(p(n)) fraction of n-bit strings). In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography.