General Math Colloquium: Lisa Kohl
Generating Pseudorandomness: Limitations and New Constructions
Our next meeting of the General Mathematics Colloquium series at the Korteweg-de Vries Institute for Mathematics will be Wednesday, March 19 at 16.00. Lisa Kohl (CWI) will speak on "Generating Pseudorandomness: Limitations and New Constructions".
Event details from: General Math Colloquium: Lisa Kohl
- Date
- 19 March 2025
- Time
- 16:00
- Room
- F3.20
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.