0
$\begingroup$

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 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 - is it pseudorandom or not, and where is the error in my thinking in either case?

$\endgroup$
  • $\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 at 19:30
0
$\begingroup$

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

$\endgroup$

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.