# Are the following functions pseudorandom?

1. 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.

1. 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.

## 2 Answers

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).

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| > \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| > \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| > \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'$.

I started writing a long proof, but then I remembered pseudorandom functions are length-preserving, so neither of these functions is a pseudorandom function. That said, they might be pseudorandom generators.

• There is no reason whatsoever to restrict PRFs to be length preserving. – Maeher Apr 23 '18 at 1:15
• That's how they are defined in Oded Goldreich's "Foundations of Cryptography" Volume I (p. 150), as well as on Wikipedia en.wikipedia.org/wiki/Pseudorandom_function_family . – fowlslegs Apr 23 '18 at 1:23
• PRFs dont need to preserve length. – user123 Apr 23 '18 at 6:04
• Please cite an academic cryptography text to support your claims. I'll cite a second "Introduction to Modern Cryptography" by Jonathan Katz and Yehuda Lindell (who incidentally posts here crypto.stackexchange.com/users/25354/yehuda-lindell ), first edition, page 87. These are both very well-respected texts. I'm curious where you've read PRFs do not needs to be length-preserving. – fowlslegs Apr 23 '18 at 7:19
• Okay, so according to Goldreich (p. 158), these constructions are indeed "efficiently computable generalized pseudorandom function ensembles (generalizable pseudorandom functions)." I'll update my answer tomorrow because I'm pretty sure I have a correct proof that the first is an efficiently computable generalized pseudorandom function ensemble. – fowlslegs Apr 23 '18 at 8:57