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:&...
| Asıl Yazarlar: | , |
|---|---|
| Materyal Türü: | Conference item |
| Dil: | English |
| Baskı/Yayın Bilgisi: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2021
|