Welcome to the resource topic for 2024/399
Title:
A Direct PRF Construction from Kolmogorov Complexity
Authors: Yanyi Liu, Rafael Pass
Abstract:While classic result 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(\cdot), and a polynomial time-bound, t(\cdot), \mktp[s] denotes the language consisting of strings x with t-bounded Kolmogorov complexity, K^t(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[2^{O(\sqrt{\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.
ePrint: https://eprint.iacr.org/2024/399
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .