Paper 2024/399
A Direct PRF Construction from Kolmogorov Complexity
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
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2024
- Contact author(s)
-
yl2866 @ cornell edu
rafaelp @ tau ac il - History
- 2024-03-05: approved
- 2024-03-04: received
- See all versions
- Short URL
- https://ia.cr/2024/399
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/399, author = {Yanyi Liu and Rafael Pass}, title = {A Direct {PRF} Construction from Kolmogorov Complexity}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/399}, year = {2024}, url = {https://eprint.iacr.org/2024/399} }