# Proving a function is or is not a pseudorandom function F_k(x) = F_k(x)||0

I have 4 functions to analyze. I need to determine if they are or are not pseudorandom and give a proof/counterexample. I'm having trouble just determining if they are - let alone proving or giving counterexamples. For reference, I'm using Katz and Lindell:

(a) $$F^1_k(x) = F_k(x) \mathbin\| 0$$

I think this is pseudorandom, proving by reduction: Suppose $$F^1$$ is not pseudorandom. Then there exists a distinguisher $$D'$$ s.t. $$\forall \mathit{negl}(n)$$, $$\bigl|P(D'^{F^1_k(\cdot)}(1^n) = 1) - P(D'^{f(\cdot)}(1^n) = 1)\bigr| > \mathit{negl}(n).$$

We can then use $$D'$$ to build a new distinguisher that attacks $$F$$. Consider discriminator $$D$$. $$D$$ gives the oracle input $$S$$ and the oracle returns output from $$F_k$$ or random output. $$D$$ adds a 0 to the end of this output and then asks $$D'$$ to determine if it is random or from $$F'$$. If $$D'$$ says random, $$D$$ says random. If $$D'$$ says not random, $$D$$ says not random. Thus:

\begin{align*} P(D^{F_k(\cdot)}(1^n) = 1) &= P(D'^{F^1_k(\cdot)}(1^n) = 1), \\ P(D^{f(\cdot)}(1^n) = 1) &= P(D'^{f(\cdot)}(1^n) = 1). \tag{*} \end{align*}

So:

$$\begin{multline*} \bigl|P(D^{F_k(\cdot)}(1^n) = 1)-P(D^{f(\cdot)}(1^n) = 1)\bigr| \\ = \bigl|P(D'^{F^1_k( \cdot)}(1^n) = 1) - P(D'^{f(\cdot )}(1^n) = 1)\bigr| > \mathit{negl}(n). \end{multline*}$$

Which contradicts that $$F_k$$ is a pseudorandom function.

On the other hand, clearly, output from $$F^1$$ always ends in 0, so the discriminator could use this fact to gain an advantage. If the output from the oracle ends in 0 he would guess that the oracle was actually $$F^1$$, if not he guesses that it is random. He would therefore have a non-negligible chance of getting this correct.

So, my question: is it pseudorandom or not, and where is the error in my thinking in either case?

• What's the output distribution of a random function oracle? What's the output distribution of your simulated oracle in that case? – Maeher Sep 19 '19 at 19:30
• How often does an output of $F^1$ end in 0? How often does a uniformly chosen string end in 0? – Mikero Feb 16 '20 at 21:50

You have shown a distinguisher for $$F^1$$ with high advantage that does not involve a distinguisher for $$F$$, so you can conclude there must be an error in your argument that that any distinguisher for $$F^1$$ implies a nearly-as-good distinguisher for $$F$$.
In particular, in equation $$(*)$$, you have confounded a uniform random function with the codomain of $$F$$ and a uniform random function with the codomain of $$F^1$$ by calling them both $$f(\cdot)$$. It may be helpful to label the codomain sizes, or at least to call it $$f$$ vs. $$f^1$$, and clearly write out the distinction between the two and how your distinguisher acts on $$f(x)\mathbin\| 0$$, $$f^1(x)$$, and $$F^1_k(x)$$.