# A question about the definition of PRFs

Let $$\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|}$$.

We define a family of functions $$\mathcal{H} = \{ h_{s} \}_{s \in \{\, 0,1 \,\}^{*}}$$, where $$h_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$$ and $$h_{s}\left( \cdot \right) = f_{s}\left( f_{s} \left( \cdot \right) \right)$$.

Let $$F_{n}$$ ($$H_{n}$$) be the distribution of functions $$f_{s}$$ ($$h_{s}$$), where $$s$$ is uniformly distributed over $$\{\, 0,1 \,\}^{n}$$. And let $$R_{n}$$ denote the uniform distribution over the set of all functions from $$\{\, 0,1 \,\}^{n}$$ to $$\{\, 0,1 \,\}^{n}$$.

We know that for any PPT adversary $$A$$, if for all $$n$$, $$\left\vert \Pr\left[ A^{F_{n}}\left( 1^n \right) = 1 \right] - \Pr\left[ A^{R_{n}}\left( 1^n \right) = 1 \right] \right\vert \leq \epsilon (n)$$ then $$\mathcal{F}$$ is a family of PRFs. And if $$\mathcal{F}$$ is a family of PRFs, then $$\mathcal{H}$$ is also a family of PRFs.

How about $$A$$ can only can query the oracle of a function sampled only one time? In other words, if $$\left\vert \Pr\left[ A\left( F_{n} \right) = 1 \right] - \Pr\left[ A\left( R_{n} \right) = 1 \right] \right\vert \leq \epsilon (n)$$ holds true, can we get that $$\left\vert \Pr\left[ A^{F_{n}}\left( 1^n \right) = 1 \right] - \Pr\left[ A^{R_{n}}\left( 1^n \right) = 1 \right] \right\vert \leq \epsilon (n)$$

PS: The title may not clear enough, but I don't know how to make it better :(. Thanks for anyone helping me to make it better :).

• There's something wrong with your question setup. A PRF takes two inputs: a value in $\{0,1\}^n$, and a key. Your function $f_n$ takes only one input. So, syntactically, it can't be a PRF. It's also not clear to me what you mean by "the distribution of functions $f_n$". You might want to check your understanding of the definitions. Once you fix that up, you'll find that a simple counterexample is $f(k,x) = k \oplus x$. – D.W. Feb 27 '18 at 16:33
• @D.W. You are right, I wrote the correct definition at the first time, and I decided to simplify it. And I did not realize that it is wrong. – TeamBright Mar 3 '18 at 7:33

Let $F_n$ be a random involution induced by a random perfect matching on $\{0,1\}^n$. For any input $x$, the distributions of $F_n(x)$ and $R_n(x)$ are almost identical (in fact, $F_n(x)$ has the same distribution as $R_n(x)$ conditioned on the event $R_n(x) \neq x$, which occurs with probability $1-2^{-n}$), so they are statistically indistinguishable. However, $H_n$ is the identity function, so it is easy to distinguish from a random function.
• There is a one more question about the definition, can you help me? The definition of PRFs in wiki says that $F_{n}$ is the distribution of functions $f_{s}$, where $s$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$. But as I know, $F_{n}$ is the distribution of functions $f_{s}$, where $s$ if fixed at first, right? Does the definition correct? – TeamBright Mar 4 '18 at 7:45
• If $s$ is fixed then the distribution is concentrated on a single function! What would $s$ be fixed to? Rather, you should think of $s$ as a key or randomness which is used to generate the function. If this confuses you, I suggest reading $f$ instead of $f_s$. – Yuval Filmus Mar 4 '18 at 10:41
• Let $D_{1}$ and $D_{2}$ be two distributions. I notice even though they are statistically indistinguishable, maybe there still exists an oracle algorithm $D$ which can distinguish them. Why? I think that two distributions are statistically indistinguishable means that they cannot be distinguished even if $D$ has infinite power. – TeamBright Mar 6 '18 at 7:31
• Two distributions are statistically indistinguishable if their statistical distance is negligible (smaller than inverse polynomial). The statistical distance is the advantage of the best algorithm which tries to separate the two distributions (i.e., the maximum of $|\Pr[D(D_1)=1] - \Pr[D(D_2)=1]|$ over all oracle algorithms $D$). – Yuval Filmus Mar 6 '18 at 12:33