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:&...
| Principais autores: | , |
|---|---|
| Formato: | Conference item |
| Idioma: | English |
| Publicado em: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2021
|