👂🏽 👤 🌀 Accidents are not random: who are the families of pseudo-random functions (PRFs) 👩🏻‍⚕️ 👵🏽 👨🏻

In 1984, Goldreich, Goldwasser, and Micali formalized the concept of pseudo-random functions and proposed a PRF implementation based on a length doubling pseudo-random generator (PRG). Since then, pseudo-random functions have proven to be an extremely important abstraction that has found applications in various fields, such as message authentication and theorem proving. In this article I will explain:

What are random functions (RF)
What are pseudo-random functions (PRF)
Who are these families of yours?
PRF vs. PRG
What does block ciphers have to do with it?

Randomness

Already from the name it becomes clear that a pseudo-random function is something that "looks" like a random function. Well, what is a random function in our case? To begin with, we will restrict our scope of consideration by functions displaying a string of zeros and ones of length in a string of zeros and ones of the same length , that is

$\ underbrace {1110 ... 0010} _ {n} \ rightarrow \ underbrace {0100 ... 0011} _ {n} \ Leftrightarrow \ {0,1 \} ^ n \ rightarrow \ {0,1 \} ^ n$

Generally speaking, this can be omitted, and we can consider mappings of strings of one length to strings of another length, but in this case one will have to pay attention to differences in dimensions. Next, we introduce the set of all functions that perform the mapping $\ {0,1 \} ^ n \ rightarrow \ {0,1 \} ^ n$ and denote it $\ text {Func} _n$ .

Consider the cardinality of this set. Obviously $| {\ text {Func} _n} | = 2 ^ {n2 ^ n}$ .

$\ text {Total distinct strings of length} n \ space - \ space 2 ^ n.$ $\ text {To store} 2 ^ n \ text {lines you need} n2 ^ n \ text {bits.}$ $\ text {These} n2 ^ {n} \ text {bits and will set the desired mapping} 2 ^ n \ text {lines.}$ $\ text {And there will be a total of such mappings} 2 ^ {n2 ^ n}.$

. – $\ text {Func} _n$ . , 2 ^ n - 2 ^ n . ,