Cryptology ePrint Archive: Report 2020/423

On One-way Functions and Kolmogorov Complexity

Yanyi Liu and Rafael Pass

Abstract: We prove that the following are equivalent:

- Existence of one-way functions: the existence of one-way functions (which in turn are equivalent to PRGs, pseudo-random functions, secure encryptions, digital signatures, commitment schemes, and more).

- Mild average-case hardness of $K^{poly}$-complexity: the existence of polynomials $t,p$ such that no PPT algorithm can determine the $t$-time bounded Kolmogorov Complexity, $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.

Category / Keywords: foundations / one-way functions, Kolmogorov complexity, average-case hardness

Date: received 14 Apr 2020, last revised 24 Apr 2020

Contact author: yl2866 at cornell edu,rafael@cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20200424:221643 (All versions of this report)

Short URL: ia.cr/2020/423


[ Cryptology ePrint archive ]