CryptoDB
One-way Functions and the Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2023 |
| Abstract: | Consider the recently introduced notion of \emph{probabilistic time-bounded Kolmogorov Complexity}, $pK^t$ (Goldberg et al, CCC'22), and let $\mpktp$ denote the language of pairs $(x,t)$ such that $pK^t(x) \leq t$. We show the equivalence of the following: \BI \item $\mpkpolyp$ is (mildly) hard-on-average w.r.t. \emph{any} samplable distribution $\D$; \item $\mpkpolyp$ is (mildly) hard-on-average w.r.t. the \emph{uniform} distribution; \item existence of one-way functions. \EI As far as we know, this yields the first natural class of problems where hardness with respect to any samplable distribution is equivalent to hardness with respect to the uniform distribution. Under standard derandomization assumptions, we can show the same result also w.r.t. the standard notion of time-bounded Kolmogorov complexity, $K^t$. |
BibTeX
@inproceedings{crypto-2023-33268,
title={One-way Functions and the Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-38545-2_21},
author={Yanyi Liu and Rafael Pass},
year=2023
}