One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions

Yanyi Liu; Rafael Pass

Paper 2023/1591

One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions

Yanyi Liu, Cornell Tech

Rafael Pass, Tel-Aviv University, Cornell Tech

Abstract

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published by the IACR in CRYPTO 2023
Contact author(s): yl2866 @ cornell edu
rafaelp @ tau ac il
History: 2023-10-17: approved; 2023-10-13: received; See all versions
Short URL: https://ia.cr/2023/1591
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1591,
      author = {Yanyi Liu and Rafael Pass},
      title = {One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1591},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1591}
}