I am new to cryptography. I have question regarding the size of the set of random functions. I found the text from "Introduction to modern cryptography" by Katz and Lindell, in another thread which also relates to my question: Difference between Pseudorandom Function vs randomly chosen function
The text from "Introduction to modern cryptography" by Katz and Lindell (chapter 3.5.1) from the thread:
Since the notion of choosing a function at random is less familiar than the notion of choosing a string at random, it is worth spending a bit more time on this idea. From a mathematical point of view, we can consider the set $\text{Func}_n$ of all functions mapping $n$ -bit strings to $n$ -bit strings; this set is finite (as we will see in a moment), and so randomly selecting a function mapping $n$ -bit strings to $n$ -bit strings corresponds exactly to choosing an element uniformly at random from this set.
How large is the set $\text{Func}_n$ ? A function $f$ is exactly specified by its value on each point in its domain; in fact, we can view any function (over a finite domain) as a large look-up table that stores $f(x)$ in the row of the table labeled by $x$ . For $f \in\text{Func}_n$ , the look-up table for $f$ has $2^n$ rows (one for each point of the domain $\{0,1\}^n$ ) and each row contains an $n$ -bit string (since the range of $f$ is ${0,1}^n$ ). Any such table can thus be represented using exactly $n\cdot 2^n$ bits.
Moreover, the functions in $\text{Func}_n$ are in one-to-one correspondence with look-up tables of this form; meaning that they are in one-to-one correspondence with all strings of length $n\cdot 2^n$.
We conclude that the size of $\text{Func}_n$ is $2^{(n\cdot 2^n)}$. ...
Assume $n = 2$
Than we have following mapping
00 00
01 01
10 10
11 11
00 11
01 00
10 01
11 10
00 10
01 11
10 00
11 01
00 01
01 10
10 11
11 00
if we rearrange so that each each row of $f(x)$ corresponds to each $x$. i.e. concatenating we will have following rows.
00 01 10 11
11 00 01 10
10 11 00 01
01 10 11 00
Each row will contain $n\cdot2^n$ bits. i.e. our case $2\cdot2^2 = 8$. And according to my estimate(perhaps incorrect) total number of bits will be $2^n\cdot n\cdot2^n = n\cdot2^{2\cdot n} = 32$.
While text states the size is $2^{n\cdot2^n}$ i.e. $256$? Could you please help me to find what I missed in my assumptions and where is my mistake?
