Abstract

Randomness is essential in cryptography, forming the foundation of secure communication and advanced privacy-preserving protocols. A key tool for generating randomness on demand is a pseudorandom function (PRF), which expands a short random seed into a virtually unbounded supply of (pseudo)randomness. But how complex do these functions need to be? Learning theory tells us that certain function classes are "easy" to learn - and therefore easy to distinguish from random - imposing fundamental limits on PRF constructions. However, even when considering function classes that are not easy to learn, constructing concrete PRF candidates that are plausibly secure remains a challenging problem. In this talk, I will introduce the concept of (weak) PRFs and explore both theoretical limitations and explicit constructions of (weak) PRFs computable by shallow circuits.