SoK: On Shallow Weak PRFs

Overview & Synopsis

A growing number of advanced cryptographic protocols and constructions rely on symmetric primitives known as weak pseudo-random functions (wPRFs). 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. In practice, many of these functions are implemented as shallow, non-iterated constructions with simple circuit representations.This Systematization of Knowledge (SoK) provides a unified view of shallow wPRFs (swPRFs), which we define as wPRFs computable by low-depth circuits and primarily used in different secure computation protocols. We identify and classify four main families of swPRFs—alternating moduli wPRFs, Goldreich’s PRG family, and the VDLPN and EALPN constructions—presenting formal definitions, algorithmic descriptions, known variants, cryptanalytic results, and concrete parameter sets for each.In addition to surveying the literature, our goal is to shift the focus from asymptotic analyses to concrete cryptanalysis. To this end, we provide a set of cryptanalytic challenges along with reference SAGE implementations for all the primitives discussed. We aim to encourage the symmetric cryptography community—particularly cryptanalysts— to rigorously evaluate the practical security levels offered by swPRFs, as concrete analyses are currently lacking. Given their growing use in high-level protocols and constructions, any cryptanalytic breakthrough on these primitives could directly affect the security of the broader cryptographic systems that rely on them.