I am currently going through a course in cryptography. In this, I stumbled upon Pseudorandom Functions. I got a little idea of Pseudorandom Generators which map an input string (key) to an extended string. However, I do not understand the pseudorandomness in case of a function.

In the book Introduction to modern cryptography by Katz and Lindell, I found this:

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 $\operatorname{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 $\operatorname{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_n\in\operatorname{Func}n$, the look-up table for $f_n$ 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_n$ is $\{0,1\}^n$). Any such table can thus be represented using exactly $n\cdot2^n$ bits.

Moreover, the functions in $\operatorname{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\cdot2^n$.

We conclude that the size of $\operatorname{Func}n$ is $2^{n\cdot2^n}$ . Viewing a function as a look-up table provides another useful way to think about selecting a function $f_n\in\operatorname{Func}n$ uniformly at random. Indeed, this is exactly equivalent to choosing each row of the look-up table of $f_n$ uniformly at random. That is, the values $f_n(x)$ and $f_n(y)$ (for $x\neq y$) are completely independent and uniformly distributed.

Coming back to our discussion of pseudorandom functions, recall that we wish to construct a keyed function $F$ such that $F_k$ (for $k\gets\{0, 1\}^n$ chosen uniformly at randomly) is indistinguishable from $f_n$ (for $f_n\gets\operatorname{Func}n$ chosen uniformly at random). Note that the former is chosen from a distribution over (at most) $2^n$ distinct functions, whereas the latter is chosen from a distribution over all $2^{n\cdot2^n}$ functions in $\operatorname{Func}n$. Despite this, the "behavior" of these functions must look the same to any polynomial-time distinguisher. A first attempt at formalizing the notion of a pseudorandom function would

Can anyone please explain me this concept in easier terms?

I am currently going through a course in cryptography. In this, I stumbled upon Pseudorandom Functions. I got a little idea of Pseudorandom Generators which map an input string (key) to an extended string. However, I do not understand the pseudorandomness in case of a function.

In the book Introduction to modern cryptography by Katz and Lindell, I found this:

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 $\operatorname{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 $\operatorname{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_n\in\operatorname{Func}n$, the look-up table for $f_n$ 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_n$ is $\{0,1\}^n$). Any such table can thus be represented using exactly $n\cdot2^n$ bits.

Moreover, the functions in $\operatorname{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\cdot2^n$.

We conclude that the size of $\operatorname{Func}n$ is $2^{n\cdot2^n}$ . Viewing a function as a look-up table provides another useful way to think about selecting a function $f_n\in\operatorname{Func}n$ uniformly at random. Indeed, this is exactly equivalent to choosing each row of the look-up table of $f_n$ uniformly at random. That is, the values $f_n(x)$ and $f_n(y)$ (for $x\neq y$) are completely independent and uniformly distributed.

Coming back to our discussion of pseudorandom functions, recall that we wish to construct a keyed function $F$ such that $F_k$ (for $k\gets\{0, 1\}^n$ chosen uniformly at randomly) is indistinguishable from $f_n$ (for $f_n\gets\operatorname{Func}n$ chosen uniformly at random). Note that the former is chosen from a distribution over (at most) $2^n$ distinct functions, whereas the latter is chosen from a distribution over all $2^{n\cdot2^n}$ functions in $\operatorname{Func}n$. Despite this, the "behavior" of these functions must look the same to any polynomial-time distinguisher.

Can anyone please explain me this concept in easier terms?

I am currently going through a course in cryptography. In this, I stumbled upon Pseudorandom Functions. I got a little idea of Pseudorandom Generators which map an input string (key) to an extended string. However, I do not understand the pseudorandomness concept in case of a function.

In the book Introduction to modern cryptography by Katz and Lindell, I found this:

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 $\operatorname{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 $\operatorname{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_n\in\operatorname{Func}n$, the look-up table for $f_n$ 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_n$ is $\{0,1\}^n$). Any such table can thus be represented using exactly $n\cdot2^n$ bits. Moreover, the functions in $\operatorname{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\cdot2^n$. We conclude that the size of $\operatorname{Func}n$ is $2^{n\cdot2^n}$ . Viewing a function as a look-up table provides another useful way to think about selecting a function $f_n\in\operatorname{Func}n$ uniformly at random. Indeed, this is exactly equivalent to choosing each row of the look-up table of $f_n$ uniformly at random. That is, the values $f_n(x)$ and $f_n(y)$ (for $x\neq y$) are completely independent and uniformly distributed. Coming back to our discussion of pseudorandom functions, recall that we wish to construct a keyed function $F$ such that $F_k$ (for $k\gets\{0, 1\}^n$ chosen uniformly at randomly) is indistinguishable from $f_n$ (for $f_n\gets\operatorname{Func}n$ chosen uniformly at random). Note that the former is chosen from a distribution over (at most) $2^n$ distinct functions, whereas the latter is chosen from a distribution over all $2^{n\cdot2^n}$ functions in $\operatorname{Func}n$. Despite this, the "behavior" of these functions must look the same to any polynomial-time distinguisher. A first attempt at formalizing the notion of a pseudorandom function would

Can anyone please explain me this concept in easier terms?

I am currently going through a course in cryptography. In this, I stumbled upon Pseudorandom Functions. I got a little idea of Pseudorandom Generators which map an input string (key) to an extended string. However, I do not understand the pseudorandomness in case of a function.

In the book Introduction to modern cryptography by Katz and Lindell, I found this:

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 $\operatorname{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 $\operatorname{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_n\in\operatorname{Func}n$, the look-up table for $f_n$ 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_n$ is $\{0,1\}^n$). Any such table can thus be represented using exactly $n\cdot2^n$ bits. 

Moreover, the functions in $\operatorname{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\cdot2^n$. 

We conclude that the size of $\operatorname{Func}n$ is $2^{n\cdot2^n}$ . Viewing a function as a look-up table provides another useful way to think about selecting a function $f_n\in\operatorname{Func}n$ uniformly at random. Indeed, this is exactly equivalent to choosing each row of the look-up table of $f_n$ uniformly at random. That is, the values $f_n(x)$ and $f_n(y)$ (for $x\neq y$) are completely independent and uniformly distributed.

Coming back to our discussion of pseudorandom functions, recall that we wish to construct a keyed function $F$ such that $F_k$ (for $k\gets\{0, 1\}^n$ chosen uniformly at randomly) is indistinguishable from $f_n$ (for $f_n\gets\operatorname{Func}n$ chosen uniformly at random). Note that the former is chosen from a distribution over (at most) $2^n$ distinct functions, whereas the latter is chosen from a distribution over all $2^{n\cdot2^n}$ functions in $\operatorname{Func}n$. Despite this, the "behavior" of these functions must look the same to any polynomial-time distinguisher. A first attempt at formalizing the notion of a pseudorandom function would

Can anyone please explain me this concept in easier terms?

I am currently going through a course in cryptography. In this, i stumbled upon Pseudorandom functions. I got little idea on Pseudorandom generator which maps an input string (key) into an extended string. However, i do not understand the pseodo concept in case of function.

Referring, the book Introduction to modern cryptography by Katz,lindell , i found this .

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 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 Funcn ? 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 fn ∈ Funcn , the look-up table for fn has 2n rows (one for each point of the domain {0, 1}n ) and each row contains an n-bit string (since the range of fn is {0, 1}n ). Any such table can thus be represented using exactly n · 2n bits. Moreover, the functions in Funcn are in one-to-one correspondence with look-up tables of this form; meaning that they are in one-to-one correspondence n with all strings of length n · 2 n. We conclude that the size of Funcn is 2n·2 . Viewing a function as a look-up table provides another useful way to think about selecting a function fn ∈ Funcn uniformly at random. Indeed, this is exactly equivalent to choosing each row of the look-up table of f n uniformly at random. That is, the values fn(x) and fn(y) (for x = y) are completely independent and uniformly distributed. Coming back to our discussion of pseudorandom functions, recall that we wish to construct a keyed function F such that Fk (for k ← {0, 1}n chosen uniformly at randomly) is indistinguishable from fn (for fn ← Funcn chosen uniformly at random). Note that the former is chosen from a distribution over (at most) 2n distinct functions, whereas the latter is chosen from a distribu- tion over all 2n·2n functions in Funcn . Despite this, the “behavior” of these functions must look the same to any polynomial-time distinguisher. A first attempt at formalizing the notion of a pseudorandom function would

Can anyone please explain me this concept in easier terms  ?

Thanks in advance.

I am currently going through a course in cryptography. In this, I stumbled upon Pseudorandom Functions. I got a little idea of Pseudorandom Generators which map an input string (key) to an extended string. However, I do not understand the pseudorandomness concept in case of a function.

In the book Introduction to modern cryptography by Katz and Lindell, I found this:

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 $\operatorname{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 $\operatorname{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_n\in\operatorname{Func}n$, the look-up table for $f_n$ 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_n$ is $\{0,1\}^n$). Any such table can thus be represented using exactly $n\cdot2^n$ bits. Moreover, the functions in $\operatorname{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\cdot2^n$. We conclude that the size of $\operatorname{Func}n$ is $2^{n\cdot2^n}$ . Viewing a function as a look-up table provides another useful way to think about selecting a function $f_n\in\operatorname{Func}n$ uniformly at random. Indeed, this is exactly equivalent to choosing each row of the look-up table of $f_n$ uniformly at random. That is, the values $f_n(x)$ and $f_n(y)$ (for $x\neq y$) are completely independent and uniformly distributed. Coming back to our discussion of pseudorandom functions, recall that we wish to construct a keyed function $F$ such that $F_k$ (for $k\gets\{0, 1\}^n$ chosen uniformly at randomly) is indistinguishable from $f_n$ (for $f_n\gets\operatorname{Func}n$ chosen uniformly at random). Note that the former is chosen from a distribution over (at most) $2^n$ distinct functions, whereas the latter is chosen from a distribution over all $2^{n\cdot2^n}$ functions in $\operatorname{Func}n$. Despite this, the "behavior" of these functions must look the same to any polynomial-time distinguisher. A first attempt at formalizing the notion of a pseudorandom function would

Can anyone please explain me this concept in easier terms?