期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that one-way functions exist if and only if there is some samplable distribution D such that it is hard to approximate the Kolmogorov complexity of a string sampled from D. Thus we characterize the existence of one-way functions by the average-case hardness of a natural \emph{uncomputable} problem on samplable distributions, extending a recent line of work by Liu and Pass (FOCS'20, STOC'21) and Ren and Santhanam (CCC'21). We also show that the average-case hardness of approximating Minimum Circuit Size on a locally samplable distribution (where the sampler runs in sub-linear time by using random access to its input) is equivalent to the existence of one-way functions. This is the first characterization of one-way functions by a natural average-case hardness assumption on the Minimum Circuit Size Problem. We present several other characterizations and connections between one-way functions and average-case hardness of meta-complexity problems (problems about complexity) on samplable distributions. We give various applications of these results to the foundations of cryptography and the theory of meta-complexity. We show that the average-case hardness of deciding k-SAT or Clique on any samplable distribution of high enough entropy implies the existence of one-way functions. Thus one-way functions follow from general assumptions on the average-case hardness of NP-complete problems. We observe that our assumptions are implied by standard cryptographic assumptions such as the Planted Clique hypothesis and the pseudorandomness of Goldreich's local functions. Our results imply a range of \emph{equivalences} between various meta-complexity problems, showing that the theory of meta-complexity is very \emph{robust} when considering average-case complexity. We use our results to unconditionally solve various meta-complexity problems in CZK (computational zero-knowledge) on average, and give implications of our results for the classic question of proving NP-hardness for the Minimum Circuit Size Problem.
