Which definition of PRFs is correct?

Question

Assume the $\mathcal{F} = \{\, f_{s} \,\}_{s \in \{\, 0,1 \,\}^{*}}$ be a family of computable functions, where $f_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$.

Let $F_{n}$ be a distribution of functions $f_s$ where $s$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$, and let $RF_n$ denote the uniform distribution over the set of all functions from $\{\, 0,1 \,\}^n$ to $\{\, 0,1 \,\}^n$.

So, $F_{n} = f_{\{\, 0,1 \,\}^{n}}(x)$ for a fixed $x \in \{\, 0,1 \,\}^{n}$, right?

Then we say $\mathcal{F}$ is a family of PRFs if for every PPT $A$, $$\left\vert \Pr \left[ A^{F_{n}}\left( 1^{n} \right) = 1 \right] - \Pr \left[ A^{RF_{n}}\left( 1^{n} \right) = 1 \right] \right\vert < \varepsilon \left( n \right)$$

This definition is seems correct, but it implies that $A$ can ask the query of $f_{s}$ for at most $poly(n)$ times, $s$ may be different, but $x$ is always the same. It looks strange.

How about let $F^{\prime}_{n}$ be distribution of functions $f_s$ whose input $x$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$ with any fixed $s$, and let $RF^{\prime}_n$ denote the uniform distribution over the set $\{\, 0,1 \,\}^n$.

So $F^{\prime}_{n} = f_{s}\left( \{\, 0,1 \,\}^{n} \right)$ for a fixed $s \in \{\, 0,1 \,\}^{n}$, right?

Then we say $\mathcal{F}$ is a family of PRFs if for every PPT $A$, $$\left\vert \Pr \left[ A^{F^{\prime}_{n}}\left( 1^{n} \right) = 1 \right] - \Pr \left[ A^{RF^{\prime}_{n}}\left( 1^{n} \right) = 1 \right] \right\vert < \varepsilon \left( n \right)$$

This definition implies that $A$ can ask the query of $f_{s}$ for a fixed key $s$ at most $poly(n)$ times.

Is the first definition is correct? Why not choose the another one?

Or even they are both wrong, $F_{n} = f_{\{\, 0,1 \,\}^{n}}\left( \{\, 0,1 \,\}^{n} \right)$?? It makes me confused.

Answer 1

So, $F_{n} = f_{\{\, 0,1 \,\}^{n}}(x)$ for a fixed $x \in \{\, 0,1 \,\}^{n}$, right?

Nope. That's not right. Consider the set of functions $\{f_s : s \in \{0,1\}^n\}$. According to what you have written, $F_n$ is a random variable that is drawn uniformly at random from that set. (I find this a confusing choice of notation, but I'm going with your proposed definitions.)

This definition is seems correct, but it implies that $A$ can ask the query of $f_{s}$ for at most $poly(n)$ times, $s$ may be different, but $x$ is always the same. It looks strange.

Actually, what it means is that $s$ is the same for every query, but $x$ can be different for each query. Yes, $A$ can only ask polynomially queries -- that's a crucial restriction.

How about let $F_{n}$ be distribution of functions $f_s$ whose input $x$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$

First off: Please don't redefine the meaning of existing notation. $F_n$ was already defined to mean something else. Don't define it to mean two different things in two different parts of your post. That's just confusing.

Second, that definition doesn't make sense. There's nothing such thing as a function whose input is uniformly distributed over something. That doesn't make sense. A function is a function; its a mapping from inputs to outputs. You don't get to specify an input distribution; a function is whatever it is. Think of a function as a truth table -- there's no way to specify an input distribution, as that's not part of the definition of a function.

---

I suggest finding a textbook on theoretical cryptography -- e.g., Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell -- and follow the definitions there. I wouldn't recommend relying upon Wikipedia for definitions or to learn from.