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| &gt; \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) &amp;= P(D'^{F^1_k(\cdot)}(1^n) = 1), \\
  P(D^{f(\cdot)}(1^n) = 1) &amp;= 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|
    &gt; \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?
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)$.