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*}


\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?

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.