Christina Boura
IRIF, CNRS, Université Paris Cité, Paris, France

Geoffroy Couteau
IRIF, CNRS, Université Paris Cité, Paris, France

Léo Perrin
Inria, Paris, France

Yann Rotella
Université Paris-Saclay, UVSQ, CNRS, Laboratoire de Mathématiques de Versailles, Versailles, France

Keywords: shallow weak PRFs, alternating moduli, Goldreich's PRG, VDLPN, EALPN

Abstract

A growing number of advanced cryptographic protocols and constructions rely on symmetric primitives known as weak pseudorandom functions. These functions differ significantly from traditional PRFs: they operate in constrained models where inputs are sampled uniformly at random and are not chosen by the adversary, and many are shallow, non-iterated constructions with simple circuit representations. This Systematization of Knowledge provides a unified view of shallow weak PRFs, defined here as weak PRFs computable by low-depth circuits and primarily used in secure computation protocols. We identify and classify four main families of shallow weak PRFs, present formal definitions, algorithmic descriptions, known variants, cryptanalytic results, and concrete parameter sets, and shift the focus from asymptotic analyses toward concrete cryptanalysis. To support that goal, we provide cryptanalytic challenges together with reference SAGE implementations for all discussed primitives. The intent is to encourage the symmetric cryptography community, especially cryptanalysts, to evaluate the practical security levels of these constructions rigorously, since any breakthrough on them may directly affect the security of higher-level systems that rely on them.