Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-052 | 25th April 2020 01:16

On One-way Functions and Kolmogorov Complexity

RSS-Feed




Revision #1
Authors: Yanyi Liu, Rafael Pass
Accepted on: 25th April 2020 01:16
Downloads: 39
Keywords: 


Abstract:

We prove the equivalence of two fundamental
problems in the theory of computation:

-Existence of one-way functions: the existence of one-way functions
(which in turn is equivalent to the existence of secure private-key
encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more).
-Mild average-case hardness of $K^{\poly}$-complexity: the existence of polynomials
$t,p>0$ 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.


Paper:

TR20-052 | 14th April 2020 14:44

On One-way Functions and Kolmogorov Complexity





TR20-052
Authors: Yanyi Liu, Rafael Pass
Publication: 18th April 2020 12:44
Downloads: 211
Keywords: 


Abstract:

We prove the equivalence of two fundamental problems in the theory of computation:

- Existence of one-way functions: the existence of one-way functions (which in turn are equivalent to pseudorandom generators, pseudorandom functions, private-key encryption schemes, 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 ``non-trivial'' complexity-based Cryptography: ``Non-trivial'' complexity-based Cryptography is possible iff $K^{poly}$ is mildly hard-on average.



ISSN 1433-8092 | Imprint