Paper 2024/1104
Structural Lower Bounds on Black-Box Constructions of Pseudorandom Functions
Abstract
We address the black-box complexity of constructing pseudorandom functions (PRF) from pseudorandom generators (PRG). The celebrated GGM construction of Goldreich, Goldwasser, and Micali (Crypto 1984) provides such a construction, which (even when combined with Levin's domain-extension trick) has super-logarithmic depth. Despite many years and much effort, this remains essentially the best construction we have to date. On the negative side, one step is provided by the work of Miles and Viola (TCC 2011), which shows that a black-box construction which just calls the PRG once and outputs one of its output bits, cannot be a PRF.
In this work, we make significant further progress: we rule out black-box constructions of PRF from PRG that follow certain structural constraints, but may call the PRG adaptively polynomially many times. In particular, we define ``tree constructions" which generalize the GGM structure: they apply the PRG
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in CRYPTO 2024
- Contact author(s)
-
amos beimel @ gmail com
tal @ cs columbia edu
noammaz @ gmail com - History
- 2024-07-10: revised
- 2024-07-06: received
- See all versions
- Short URL
- https://ia.cr/2024/1104
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1104, author = {Amos Beimel and Tal Malkin and Noam Mazor}, title = {Structural Lower Bounds on Black-Box Constructions of Pseudorandom Functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1104}, year = {2024}, url = {https://eprint.iacr.org/2024/1104} }