Welcome to the resource topic for 2021/1076
Title:
Hardness of KT Characterizes Parallel Cryptography
Authors: Hanlin Ren, Rahul Santhanam
Abstract: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, {\rm K}^t, is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures: * We show, perhaps surprisingly, that the \rm KT complexity is bounded-error average-case hard if and only if there exist one-way functions in constant parallel time (i.e., {\sf 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 {\sf NC}^0-computable one-way functions exist if and only if logspace-computable one-way functions exist. * Inspired by the above result, we present randomized average-case reductions among the {\sf NC}^1-versions and logspace-versions of {\rm K}^t complexity, and the \rm 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 \rm KT complexity and a variant of {\rm K}^t complexity. * We prove tight connections between the hardness of {\rm 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 {\rm K}^t and \rm KT. We show that a Strong Perebor Hypothesis for {\rm 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. * We show that a Weak Perebor Hypothesis for {\rm 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 {\rm MCSP} over a natural distribution. * Finally, we study the average-case hardness of {\rm MKtP}. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.
ePrint: https://eprint.iacr.org/2021/1076
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .