ECCC-Report TR20-052https://eccc.weizmann.ac.il/report/2020/052Comments and Revisions published for TR20-052en-usThu, 24 Sep 2020 09:13:06 +0300
Revision 2
| On One-way Functions and Kolmogorov Complexity |
Rafael Pass,
Yanyi Liu
https://eccc.weizmann.ac.il/report/2020/052#revision2We 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.Thu, 24 Sep 2020 09:13:06 +0300https://eccc.weizmann.ac.il/report/2020/052#revision2
Revision 1
| On One-way Functions and Kolmogorov Complexity |
Rafael Pass,
Yanyi Liu
https://eccc.weizmann.ac.il/report/2020/052#revision1We 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.Sat, 25 Apr 2020 01:16:06 +0300https://eccc.weizmann.ac.il/report/2020/052#revision1
Paper TR20-052
| On One-way Functions and Kolmogorov Complexity |
Rafael Pass,
Yanyi Liu
https://eccc.weizmann.ac.il/report/2020/052We 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.
Sat, 18 Apr 2020 12:44:35 +0300https://eccc.weizmann.ac.il/report/2020/052