IACR News item: 17 October 2023
Yanyi Liu, Rafael Pass
ePrint Report
Consider the recently introduced notion of \emph{probabilistic
time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al,
CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k.
We show the equivalence of the following:
- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable
distribution D;
- MpK^{poly}P is (mildly) hard-on-average w.r.t. the
\emph{uniform} distribution;
- Existence of one-way functions.
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.
Under standard derandomization assumptions, we can show the same result also w.r.t. the standard notion of time-bounded Kolmogorov complexity, K^t.
Additional news items may be found on the IACR news page.