Welcome to the resource topic for 2025/2085
Title:
Strong Pseudorandom Functions in AC^0[2] in the Bounded-Query Setting
Authors: Marshall Ball, Clément Ducros, Saroja Erabelli, Lisa Kohl, Nicolas Resch
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.
ePrint: https://eprint.iacr.org/2025/2085
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 .