**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 ]