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:&...
| Main Authors: | , |
|---|---|
| Formato: | Conference item |
| Idioma: | English |
| Publicado em: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2021
|
| _version_ | 1826309219332128768 |
|---|---|
| author | Ren, H Santhanam, R |
| author_facet | Ren, H Santhanam, R |
| author_sort | Ren, H |
| collection | OXFORD |
| description | <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:</p>
<p>- We show, perhaps surprisingly, that the KT complexity is bounded-error average-case hard if and only if there exist one-way functions in constant parallel time (i.e. NC⁰). This result crucially relies on the idea of randomized encodings. Previously, a seminal work of Applebaum, Ishai, and Kushilevitz (FOCS'04; SICOMP'06) used the same idea to show that NC⁰-computable one-way functions exist if and only if logspace-computable one-way functions exist.</p>
<p>- Inspired by the above result, we present randomized average-case reductions among the NC¹-versions and logspace-versions of K^t complexity, and the KT complexity. Our reductions preserve both bounded-error average-case hardness and zero-error average-case hardness. To the best of our knowledge, this is the first reduction between the KT complexity and a variant of K^t complexity.</p>
<p>- We prove tight connections between the hardness of K^t complexity and the hardness of (the hardest) one-way functions. In analogy with the Exponential-Time Hypothesis and its variants, we define and motivate the Perebor Hypotheses for complexity measures such as K^t and KT. We show that a Strong Perebor Hypothesis for K^t implies the existence of (weak) one-way functions of near-optimal hardness 2^{n-o(n)}. To the best of our knowledge, this is the first construction of one-way functions of near-optimal hardness based on a natural complexity assumption about a search problem.</p>
<p>- We show that a Weak Perebor Hypothesis for MCSP implies the existence of one-way functions, and establish a partial converse. This is the first unconditional construction of one-way functions from the hardness of MCSP over a natural distribution.</p>
<p>- Finally, we study the average-case hardness of MKtP. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.</p> |
| first_indexed | 2024-03-07T07:30:52Z |
| format | Conference item |
| id | oxford-uuid:b9f74a5e-b799-4ecb-8422-95af57c4e3ba |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:30:52Z |
| publishDate | 2021 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:b9f74a5e-b799-4ecb-8422-95af57c4e3ba2023-01-19T16:47:11ZHardness of KT characterizes parallel cryptographyConference itemhttp://purl.org/coar/resource_type/c_5794uuid:b9f74a5e-b799-4ecb-8422-95af57c4e3baEnglishSymplectic ElementsSchloss Dagstuhl - Leibniz-Zentrum für Informatik 2021Ren, HSanthanam, R<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:</p> <p>- We show, perhaps surprisingly, that the KT complexity is bounded-error average-case hard if and only if there exist one-way functions in constant parallel time (i.e. NC⁰). This result crucially relies on the idea of randomized encodings. Previously, a seminal work of Applebaum, Ishai, and Kushilevitz (FOCS'04; SICOMP'06) used the same idea to show that NC⁰-computable one-way functions exist if and only if logspace-computable one-way functions exist.</p> <p>- Inspired by the above result, we present randomized average-case reductions among the NC¹-versions and logspace-versions of K^t complexity, and the KT complexity. Our reductions preserve both bounded-error average-case hardness and zero-error average-case hardness. To the best of our knowledge, this is the first reduction between the KT complexity and a variant of K^t complexity.</p> <p>- We prove tight connections between the hardness of K^t complexity and the hardness of (the hardest) one-way functions. In analogy with the Exponential-Time Hypothesis and its variants, we define and motivate the Perebor Hypotheses for complexity measures such as K^t and KT. We show that a Strong Perebor Hypothesis for K^t implies the existence of (weak) one-way functions of near-optimal hardness 2^{n-o(n)}. To the best of our knowledge, this is the first construction of one-way functions of near-optimal hardness based on a natural complexity assumption about a search problem.</p> <p>- We show that a Weak Perebor Hypothesis for MCSP implies the existence of one-way functions, and establish a partial converse. This is the first unconditional construction of one-way functions from the hardness of MCSP over a natural distribution.</p> <p>- Finally, we study the average-case hardness of MKtP. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.</p> |
| spellingShingle | Ren, H Santhanam, R Hardness of KT characterizes parallel cryptography |
| title | Hardness of KT characterizes parallel cryptography |
| title_full | Hardness of KT characterizes parallel cryptography |
| title_fullStr | Hardness of KT characterizes parallel cryptography |
| title_full_unstemmed | Hardness of KT characterizes parallel cryptography |
| title_short | Hardness of KT characterizes parallel cryptography |
| title_sort | hardness of kt characterizes parallel cryptography |
| work_keys_str_mv | AT renh hardnessofktcharacterizesparallelcryptography AT santhanamr hardnessofktcharacterizesparallelcryptography |