1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I've quickly edited your question to use MathJax. I've further used SE's citation function to make clear what is the citation and I've turned the plain mappings into code for readability. If you don't like my edits, you can edit again by clicking on "edit" in the lower left corner or you can roll my edits back by clicking on the "edited ... ago" and selecting the roll-back function. $\endgroup$ – SEJPM Aug 25 '15 at 11:37
  • 2
    $\begingroup$ You've left out the function that returns 00 on every input, and the one that returns 11 on every input, and many many others... $\endgroup$ – Chris Peikert Aug 25 '15 at 11:58
  • $\begingroup$ Or put an other way, it seems you are assuming that a function must give a unique output on each input. I.e., you are only considering injective functions. $\endgroup$ – Guut Boy Aug 25 '15 at 13:10
  • $\begingroup$ SEJPM Thank you very much. The question looks much much better after you help. $\endgroup$ – JJLee Aug 25 '15 at 16:26
  • $\begingroup$ Chris Pikert and Guut Boy many thanks! I see my mistake, but if 2^8 will be in the table should not we have same number on input. i.e. 00 00 00 00 matched with 00 00 00 00, 00 00 00 01...111111111 (256 in total). after that 00 00 00 01 matched with 00 00 00 00 ..... 111111111. Should not all the combinations be 256 * 256?. Thank you again $\endgroup$ – JJLee Aug 25 '15 at 16:37
4
$\begingroup$

Yo are taking only the one-to-one functions, while there are a lot of other functions, to name a few:

00 00
01 00  
10 00  
11 00

00 01
01 01  
10 01  
11 01

00 00
01 00  
10 01  
11 01

as you already mentioned, each table can be represented with $n*2^n$ bits, i.e. strings from the set: $\{0,1\}^{n*2^n}$, each string from this set defines one function from $Func_n$, so the number of such functions is the size of the above set $=2^{n*2^n}$

$\endgroup$
  • $\begingroup$ @fgrieu Nit: YM 24. $\endgroup$ – dave_thompson_085 Aug 25 '15 at 21:26
  • $\begingroup$ @dave_thompson_085: right; thanks; I hereby replaces my previous comment (now gone) with: Also, the enumeration of the question lists only 4 out of 4!=24 one-one functions onto the set of 2-bit strings to itself. $\endgroup$ – fgrieu Aug 25 '15 at 22:37
  • $\begingroup$ I see my mistake, but if 2^8 will be in the table should not we have same number on input. i.e. 00 00 00 00 matched with 00 00 00 00, 00 00 00 01...111111111 (256 in total). after that 00 00 00 01 matched with 00 00 00 00 ..... 111111111. Should not all the combinations be 256 * 256?. Thank you again $\endgroup$ – JJLee Aug 25 '15 at 22:51
  • $\begingroup$ You don't need to save the input explicitly, you can rely on the lexicographic order. e.g. the first 2 bits are the value of 00, the 2 bits after them are the value of 01... and so on, you don't need to write this each time, you just need to have it in your head... $\endgroup$ – Mahmoud Aug 26 '15 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.