Are the following functions pseudorandom? Given a PRF $F $, such that for each $k \in \{0,1\} \ ^ n$ , $F_k:\{0,1\} \ ^ n \to \{0,1\} \ ^ n$ , is the function defined by $W_{k_1,k_2}(x) = F_{F_{k_1(0 \ ^n )}}(x) || F_{k_2}(x)$ also a PRF? 


I'm almost sure the answer is yes.
I'm trying to assume $W$ is not a PRF and conclude that $F$ isn't either but I dont see how. 


Let F be as in (1). Now $H_k(x) = F_k(x) || F_{F_{k}(1 \ ^ n)}(F_{F_{k}(1 \ ^ n)}(F_{k}(x)))$.
I think $H$ is not a PRF.
The polynomial distinguisher I thought about is the following: 


$D$ on input $1 \ ^ n$ and orcal asses $O$ , asks for $O(1 ^ n)$ and writes $O(1 ^ n) = \alpha || \beta$ for $\alpha,\beta \in \{0,1\} \ ^ n$.
Now $D$ checks if $\beta = F_{\alpha}(F_{\alpha}(\alpha))$. if yes, outputs 1 otherwise outputs 0.

If $O=H_k$ then $D$ outputs $1$ so $Pr(D \ ^ {H_k()}(1 \ ^ n)=1 ) =1$.
If $O=h$ for a truly random functon then $D$ outputs 1 iff $F_{\alpha}(F_{\alpha}(\alpha)) = \alpha$ for $\alpha$ which is a random number in $\{0,1\} \ ^ n$.

I want to say that $Pr(F_{\alpha}(F_{\alpha}(\alpha)) = \alpha) = v(n)$ for a negl. func. and this will conclude the proof but i can't find a way to prove it. someone can help? 

Thanks for the help.
Okay, so now that we've agreed that generalized pseudorandom functions can be of variable length :-D, I'll slightly rephrase your question to meet the definitions I'm working with, and then prove (1).


Given a pseudorandom function $F = \{F_{n}\}_{n \in \mathbb{N}}$, such that for each $k \in \{0,1\}^n$ , $F_k:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$, is the function defined by $W_{k_1,k_2}(x) = F_{F_{k_1(0 \ ^n )}}(x) || F_{k_2}(x)$ a generalizable pseudorandom function?


Assume by contradiction that $W$ is not a generalizable pseudorandom function,
then there exists a probabilistic polynomial time (PPT) oracle machine $M'$ and a
polynomial $p(\cdot)$ such that for infinitely many $n$'s,

$$\big|\text{Pr}[M'^{W_{k_1,k_2}}(1^{n}) = 1] - \text{Pr}[M'^{H'_{n}}(1^{n}) = 1]\big| &gt; \frac{1}{p(n)}$$

where $k_1,k_2 \xleftarrow{\$} \{0,1\}^n$ and $H' = \{H'_n\}_{n \in \mathbb{N}}$ with $H'_n$ uniformly distributed over the set of all functions mapping $n$-bit strings to $2n$-bit strings.

We will use $M'$ to construct a PPT oracle machine $M$ to distinguish $F_k$, where $k \xleftarrow{\$} \{0,1\}^n$, from $H = \{H_n\}_{n \in \mathbb N}$, where $H_n$ is uniformly distributed over the set of all functions mapping $n$-bit strings to $n$-bit strings. On input $1^n$, $M$ first queries it's oracle $\mathcal{O}$ with the string $0^n$ and records the result as $k' \leftarrow \mathcal{O}(0^n)$. $M$ then uniformly selects $k'' \xleftarrow{\$} \{0,1\}^n$. Next $M$ runs $M'(1^n)$ and serves as its oracle, returning $F_{k'}(x)||F_{k''}(x)$ whenever $M$ queries with input $x \in \{0,1\}^n$. Whatever output $M'$ returns to $M$, $M$ outputs itself.

If $\mathcal{O} = F_k$, then

$$\text{Pr}[M^{F_k}(1^n) = 1] = \text{Pr}[M'^{F_{k'}||F_{k''}}(1^{n}) = 1] = \text{Pr}[M'^{W_{k_1,k_2}}(1^{n}) = 1]$$

since how we chose $k'$ makes our experiment identical from the point of view of $M'$ to when it's interacting with the oracle $W_{k_1,k_2}$. If $\mathcal{O} = H_n$ we have $\text{Pr}[M^{H_n}(1^n) = 1] = \text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^n) = 1]$. Now, $M'$ is a black box, and was not "designed" to distinguish $W_{k_1,k_2}$ from $F_{H_n(0^n)}||F_{k''}$. That said, we can intuitively see that $F_{H_n(0^n)}||F_{k''}$ should not be distinguishable from $H'_n$ because of our assumption that $F$ is a pseudorandom function. We will now formalize that notion.

Assume that there exists a polynomial $q(\cdot)$ such that for infinitely many $n$'s

$$\big|\text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^{n}) = 1] - \text{Pr}[M'^{H'_n}(1^{n}) = 1]\big| &gt; \frac{1}{q(n)}$$

We can then use $M'$ to construct a PPT oracle machine $M''$ to distinguish $F_k$ from $H_n$. We denote the oracle of $M''$ by $\mathcal{O}'$. On input $1^n$, $M''$ selects $k''' \xleftarrow{\$} \{0,1\}^n$ and runs $M'(1^n)$, acting as its oracle by returning $\mathcal{O}'(x)||F_{k'''}(x)$ for any query $x \in \{0,1\}^n$ that $M'$ makes.

If $\mathcal{O}' = F_k$, then

$$\text{Pr}[M''^{F_k}(1^n) = 1] = \text{Pr}[M'^{F_k||F_{k'''}}(1^n) = 1] = \text{Pr}[M'^{F_{H_n(0^n)}||F_{k''}}(1^n) = 1]$$

where the last equality follows because $k$ was chosen uniformly at random and $H_n(0^n)$ is a uniformly distributed random variable over the outputs on input $0^n$ of every function mapping $n$ bits to $n$ bits, and $k'''$ and $k''$ were both chosen uniformly at random. In the case $\mathcal{O} = H_n$ we have $\text{Pr}[M''^{H_n}(1^n) = 1] = \text{Pr}[M'^{H_n||F_{k'''}}(1^n) = 1]$. We must now go just one layer deeper before deriving a direct contradiction, and prove by contradiction that $M'$ cannot $H_n||F_{k'''}$ and $H'_n$.

Assume that there exists a polynomial $r(\cdot)$ such that for infinitely many $n$'s

$$\big|\text{Pr}[M'^{H_n||F_{k'''}}(1^{n}) = 1] - \text{Pr}[M'^{H'_n}(1^{n}) = 1]\big| &gt; \frac{1}{r(n)}$$

Since the first $n$ bits of the output of the two oracles should be uniformly distributed, they cannot provide any useful information to $M'$ to make its decision*. Then $M'$ must be able to distinguish $F_{k'''}$ from the second half of $H'_n$ with more than negligible probability. Since this is equivalent to distinguishing $F_k$ from $H_n$, it contradicts our claim that $F$ is a pseudorandom function.

Now we unfold the argument. Since $M'$ cannot distinguish $H_n||F_{k'''}$ and $H'_n$ with more than negligible probability, this contradicts our assumption that $M'$ can distinguish $F_{H_n(0^n)}||F_{k''}$ from $H'_n$ with more than negligible probability. If that assumption is wrong, then $M$ distinguishes $F_k$ from $H_n$ with only negligible difference in probability from that the which $M'$ distinguishes between $W_{k_1,k_2}$ and $H'_n$. By our hypothesis, this is non-negligible, but because we assume $F$ to be a pseudorandom function, no such $M'$ can exist. Therefore, we conclude that $W$ is a generalizable pseudorandom function.

* You could prove this more rigorously by remembering that polynomial-time unpredicability and pseudorandomness imply each other. Then show that you can replace $M'$ with a PPT oracle machine $M'''$ that never reads less than $n+1$ bits of its input (or more than $2n-1$) before guessing a bit, and that the probability that $M'''$ guesses correctly is no less than $M'$.