Pseudorandom Functions (PRFs) are among the most fundamental Cryptographic primitives. with applications as basic as private-key encryption, identification and authentication and as sophisticated as indistinguishability obfuscation (through the notion of Puncturable PRFs). PRFs were introduced in the eighties by Oded Goldreich, Shafi Goldwasser and Silvio Micali in their seminal paper “how to construct random functions.” A large fraction of papers in Cryptography rely on the GGM paper, either directly or indirectly. In particular, each one of the papers in my PhD dissertation owes its existence to GGM. So where’s the story in a paper that is universally admired and a notion that is clearly fundamental? While preparing my talk for OdedFest, I got to reread the paper and was amazed to see how much effort the authors had to put in motivating (or even justifying) PRFs. What we now take for granted was not always as obvious (and indeed, the paper was rejected from the first conference it was submitted to).

Let me first loosely define PRFs: Consider for example a family of Boolean functions on -bit strings that is efficient – it is easy (polynomial time in ) to sample a key that describes a random function from the family and given and it is easy to evaluate (in fact, the definition only makes sense if we have an ensemble of such families, one for every value of ). Such a family is pseudorandom if it is hard to distinguish from a completely random (uniformly chosen) Boolean function on bits. In other words, a distibguisher that gets black-box (oracle) access to a function cannot tell if it is or a completely random function.

PRFs allow parties to effectively share exponential number of pseudorandom bits (by sharing the parties get access to the exponentially-many outputs of ). Very powerful. Yet, GGM had to explain why Kolmogorov-Complexity based definitions are different, why PRFs are different from one-way functions and why PRFs are different from pseudorandom-bit generators. I can’t imagine any paper using PRFs today that would have to explain such basic distinctions. But even more interestingly, GGM goes to lengths to explain why PRFs are different from the following stateful simulation of a black-box random function: Assume that every past query and its answer is recorded. For every new query check if the query was previously asked and if so answer consistently, otherwise answer with a random bit and record the new pair. While I imagine that such simulation could be useful in some cases, the possibility of such simulation takes nothing from the importance of PRFs. Obvious, right? Well, it clearly wasn’t obvious to an anonymous reviewer when the paper was first submitted (and rejected).

The moral of the story is not that conference committees can be stupid, but rather that like in any other area of life, the work of the pioneers is hard. They need to justify and convince by explaining things that in retrospect seem obvious. And perhaps it is OK. After all, for every GGM there are plenty of papers offering ridiculous new notions. Nevertheless, where would we be without those innovators that keep on breaking new ground for the rest of us to follow?