Hardness of KT characterizes parallel cryptography
<p>A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity, K^t, is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures:&...
| मुख्य लेखकों: | , |
|---|---|
| स्वरूप: | Conference item |
| भाषा: | English |
| प्रकाशित: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2021
|