Paper 2025/2085

Strong Pseudorandom Functions in $AC^0[2]$ in the Bounded-Query Setting

Clément Ducros, Helmholtz Center for Information Security

Saroja Erabelli, New York University

Lisa Kohl, Centrum Wiskunde & Informatica

Nicolas Resch, University of Amsterdam

Abstract

Understanding the minimal computational power needed to realize a pseudorandom function (PRF) is a long-standing question in cryptography. By the Razborov–Smolensky polynomial approximation method, it is known that $AC^0[2]$ cannot support strong pseudorandom functions with subexponential security, since any such function can be distinguished from random with quasipolynomially many samples. In this work, we initiate the study of low-complexity strong PRFs under a refined framework that separates adversary query complexity from running time, and observe that distinguishing algorithms for $AC^0[2]$ do not apply if the number of queries is below the threshold implied by the Razborov–Smolensky approximation bound. We propose the first candidate strong PRF in $AC^0[2]$, which plausibly offers subexponential security against adversaries limited to a fixed quasipolynomial number of queries. We show that our candidate lacks heavy Fourier coefficients, resists a natural class of adaptive attacks, has high rational degree, is non-sparse over $\mathbb{F}_2$ in expectation, and has low correlation with fixed function families. Finally, we show that if any strong PRF exists in $AC^0[2]$ (or a superclass), then we can construct a universal PRF, i.e., a single, fixed function which is guaranteed to be a strong PRF in the same class.

Note: Updating acknowledgements.

@misc{cryptoeprint:2025/2085,
      author = {Marshall Ball and Clément Ducros and Saroja Erabelli and Lisa Kohl and Nicolas Resch},
      title = {Strong Pseudorandom Functions in ${AC}^0[2]$ in the Bounded-Query Setting},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2085},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2085}
}