Welcome to the resource topic for 2020/423
Title:
On One-way Functions and Kolmogorov Complexity
Authors: Yanyi Liu, Rafael Pass
Abstract:We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n)\geq (1+\varepsilon)n, \varepsilon>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, K^t, is mildly hard-on-average (i.e., there exists a polynomial p(n)>0 such that no \PPT algorithm can compute K^t, for more than a 1-\frac{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.
ePrint: https://eprint.iacr.org/2020/423
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 .