International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Direct PRF Construction from Kolmogorov Complexity

Authors:
Yanyi Liu , Cornell Tech
Rafael Pass , Tel-Aviv University and Cornell Tech
Download:
DOI: 10.1007/978-3-031-58737-5_14 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
Abstract: While classic results in the 1980s establish that one-way functions (OWFs) imply the existence of pseudorandom generators (PRGs) which in turn imply pseudorandom functions (PRFs), the constructions (most notably the one from OWFs to PRGs) is complicated and inefficient. Consequently, researchers have developed alternative \emph{direct} constructions of PRFs from various different concrete hardness assumptions. In this work, we continue this thread of work and demonstrate the first direct constructions of PRFs from average-case hardness of the time-bounded Kolmogorov complexity problem \mktp[s], where given a threshold, s(⋅), and a polynomial time-bound, t(⋅), \mktp[s] denotes the language consisting of strings x with t-bounded Kolmogorov complexity, Kt(x), bounded by s(|x|). In more detail, we demonstrate a direct PRF construction with quasi-polynomial security from mild average-case of hardness of \mktp[2O(log⁡n)] w.r.t the uniform distribution. We note that by earlier results, this assumption is known to be equivalent to the existence of quasi-polynomially secure OWFs; as such, our results yield the first direct (quasi-polynomially secure) PRF constructions from a natural hardness assumptions that also is known to be implied by (quasi-polynomially secure) PRFs. Perhaps surprisingly, we show how to make use of the Nisan-Wigderson PRG construction to get a cryptographic, as opposed to a complexity-theoretic, PRG.
BibTeX
@inproceedings{eurocrypt-2024-34024,
  title={A Direct PRF Construction from Kolmogorov Complexity},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-58737-5_14},
  author={Yanyi Liu and Rafael Pass},
  year=2024
}