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

Question

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?

Answer 1

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