ECCC-Report TR21-057https://eccc.weizmann.ac.il/report/2021/057Comments and Revisions published for TR21-057en-usSat, 21 Aug 2021 17:35:22 +0300
Revision 1
| Hardness of KT Characterizes Parallel Cryptography |
Hanlin Ren,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2021/057#revision1A 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:
1. 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^0). 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^0-computable one-way functions exist if and only if logspace-computable one-way functions exist.
2. Inspired by the above result, we present randomized average-case reductions among the NC^1-versions and logspace-versions of K^t complexity, and 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 KT complexity and a variant of K^t complexity.
3. 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.
4. 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 hardness of MCSP over a natural distribution.
5. 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.Sat, 21 Aug 2021 17:35:22 +0300https://eccc.weizmann.ac.il/report/2021/057#revision1
Paper TR21-057
| Hardness of KT Characterizes Parallel Cryptography |
Hanlin Ren,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2021/057A 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:
1. 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^0). 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^0-computable one-way functions exist if and only if logspace-computable one-way functions exist.
2. Inspired by the above result, we present randomized average-case reductions among the NC^1-versions and logspace-versions of K^t complexity, and 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 KT complexity and a variant of K^t complexity.
3. 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.
4. 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 hardness of MCSP over a natural distribution.
5. 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.Fri, 23 Apr 2021 16:36:00 +0300https://eccc.weizmann.ac.il/report/2021/057