Paper 2021/1076
Hardness of KT Characterizes Parallel Cryptography
Hanlin Ren and Rahul Santhanam
Abstract
A recent breakthrough of Liu and Pass (FOCS'20) shows that oneway functions exist if and only if the (polynomial)timebounded Kolmogorov complexity, ${\rm K}^t$, is boundederror 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 boundederror averagecase hard if and only if there exist oneway 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 oneway functions exist if and only if logspacecomputable oneway functions exist. * Inspired by the above result, we present randomized averagecase reductions among the ${\sf NC}^1$versions and logspaceversions of ${\rm K}^t$ complexity, and the $\rm KT$ complexity. Our reductions preserve both boundederror averagecase hardness and zeroerror averagecase 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) oneway functions. In analogy with the ExponentialTime 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) oneway functions of nearoptimal hardness $2^{no(n)}$. To the best of our knowledge, this is the first construction of oneway functions of nearoptimal 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 oneway functions, and establish a partial converse. This is the first unconditional construction of oneway functions from the hardness of ${\rm MCSP}$ over a natural distribution. * Finally, we study the averagecase hardness of ${\rm MKtP}$. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexitytheoretic pseudorandomness in another natural regime.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision. CCC 2021
 DOI
 10.4230/LIPIcs.CCC.2021.35
 Keywords
 oneway functionscomplexity theory
 Contact author(s)
 h4n1in r3n @ gmail com
 History
 20210824: revised
 20210823: received
 See all versions
 Short URL
 https://ia.cr/2021/1076
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1076, author = {Hanlin Ren and Rahul Santhanam}, title = {Hardness of {KT} Characterizes Parallel Cryptography}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/1076}, year = {2021}, doi = {10.4230/LIPIcs.CCC.2021.35}, url = {https://eprint.iacr.org/2021/1076} }