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

Marshall Ball; Clément Ducros; Saroja Erabelli; Lisa Kohl; Nicolas Resch; Peter Scholl

Paper 2025/2085

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

Marshall Ball

, New York University

Clément Ducros

, Helmholtz Center for Information Security

Saroja Erabelli

, New York University

Lisa Kohl

, Centrum Wiskunde & Informatica

Nicolas Resch

, University of Amsterdam

Peter Scholl

, Aarhus University

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 distinguishing advantage, 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. In this setting, we prove that strong PRFs cannot exist in the smaller class $MOD_2 \circ AC^0$, showing that every such function family can be efficiently distinguished from random using polynomially many queries. Together with the fact that functions in $AC^0 \circ MOD_2$ are conjectured to have heavy Fourier coefficients (ITCS 2014), this identifies $AC^0[2]$ as the minimal candidate class for realizing strong PRFs in the bounded-query setting. We propose the first candidate strong PRF in $AC^0[2]$, which we conjecture to offer subexponential security against adversaries limited to a fixed quasipolynomial number of queries. Furthermore, our candidate is in the class $MOD_2 \circ AC^0\circ MOD_2$, arguably the minimal class given the above barriers. We show that our candidate lacks heavy Fourier coefficients, resists many settings of linear attacks, is non-sparse over $\mathbb{F}_2$ with high probability, has high rational degree, is inapproximable by low-degree polynomials over $\mathbb{F}_2$, and has low correlation with fixed function families. As a final contribution, 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. Revised and augmented version.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Contact author(s): marshall ball @ cs nyu edu
clement ducros @ cispa de
saroja erabelli @ gmail com
lisa kohl @ cwi nl
n a resch @ uva nl
peter scholl @ cs au dk
History: 2026-07-20: last of 2 revisions; 2025-11-11: received; See all versions
Short URL: https://ia.cr/2025/2085
License: CC BY

BibTeX

@misc{cryptoeprint:2025/2085,
      author = {Marshall Ball and Clément Ducros and Saroja Erabelli and Lisa Kohl and Nicolas Resch and Peter Scholl},
      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}
}