4
$\begingroup$

I have given a pseudorandom Generator $G(s)$, $|s|=n$ whose expansion $l(n)$ is $>2n$. I also know that $G^\prime(s) := G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor})$ is a pseudorandom generator. Now the function

$\begin{equation}L(s) := G(s) ~||~ G(s+1)\end{equation}$

with $||$ being concatenation is supposed to be no pseudorandom generator and I struggle to prove it. Intuitively, I would think that since $L$ passes two different seeds to $G$ and $G$ is pseudorandom, $L$ must be pseudorandom too. $G(s+1)$ should be unpredictably different from $G(s+1)$ for a PRNG, should it not? Could someone point me into the right direction?

$\endgroup$
  • $\begingroup$ I missed the fact that you mix the terms PRG, PRF and PRNG. They are all different. Which does the problem actually concern? $\endgroup$ – otus Nov 20 '15 at 12:13
  • $\begingroup$ I am not sure what the difference is, but I would label it PRNG. $\endgroup$ – oarfish Nov 20 '15 at 12:26
  • $\begingroup$ The tag wikis (click tag, then learn more) have some info and Wikipedia has decent articles about them too. $\endgroup$ – otus Nov 20 '15 at 12:31
6
$\begingroup$

$L$ is not necessarily a pseudorandom generator, but it may be. Hence, there is no hope of proving that $L$ is not a pseudorandom generator from what you are given. Rather, you must exhibit a pseudorandom generator $G$ such that $L$ is not a pseudorandom generator. Here is the canonical example with expansion factor $n+1$.

Let $f$ be a one-way permutation (i.e., an injective, length-preserving one-way function). Then it is known that the following is a pseudorandom generator with expansion factor $n+1$:

  • Choose uniformly a seed $s$ of even length $s_1s_2\dots s_{2n}$.
  • Compute $b = \sum_{i=1}^n s_is_{n+i}$ (with arithmetic in $\mathbf{F}_2$).
  • Output $f(s_1s_2\dots s_n)s_{n+1}s_{n+2}\dots s_{2n}b$.

Now, if $s$ is uniformly chosen, with probability $1/2$ its last bit will be $0$, meaning that $s+1$ will be just $s$ with the last bit ($s_{2n}$) flipped, and in turn it means that $G(s+1)$ will equal $G(s)$ except possibly in the last two bits. Hence, a distinguisher can check whether the second half of its input string equals the first one disregarding the last two bits of each. If the string is $G(s)G(s+1)$, this happens with probability at least $1/2$, whereas if the string is truly random this happens with probability $1/2^{n-2}$.

$\endgroup$
  • $\begingroup$ Can you give a source for why it is known? $\endgroup$ – oarfish Nov 20 '15 at 13:13
  • 1
    $\begingroup$ Any good cryptography textbook (e.g., Goldreich or Katz-Lindell). $\endgroup$ – fkraiem Nov 20 '15 at 13:14
  • $\begingroup$ @fkraiem I don't think this construction is a pseudorandom generator. Since a distinguisher can always compute the last bit $b$ as described. For a uniform string the probability for last bit to be $\sum_{i=1}^n{s_is_{n+i}}$ is only $1\over2$. And as you mentioned, in Katz's book a similar construction is presented as a counterexample. $\endgroup$ – wangkaibule Jan 6 '18 at 2:33
  • $\begingroup$ @wangkaibule No, a distinguisher cannot compute $b$, since it does not know the seed (by virtue of $f$'s one-wayness). $\endgroup$ – fkraiem Jan 6 '18 at 2:58
  • $\begingroup$ @wangkaibule The generator does not output $s_1\dots s_n$; it outputs $f(s_1\dots s_n)$. $\endgroup$ – fkraiem Jan 6 '18 at 3:06
2
$\begingroup$

I eventually came up with an answer myself.

Since $|G^\prime| > 2n$, we assume $$\begin{align*} L(s) & = G^\prime(s) ~||~ G^\prime(s+1) \\ & = G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor}) ~||~ G^\prime(s+1) \\ & = G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor}) ~||~ G(s^\prime) \\ & = G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor}) ~||~ G(s^\prime_1,\ldots,s^\prime_{\lfloor\frac{n}{2}\rfloor}) \\ \end{align*}$$

Let $D(K)$ be a Distinguisher with $$\begin{equation*} D(K) = \begin{cases} 1 & \text{if $k_1,\ldots,k_{\frac{n}{2}} = k_{\frac{n}{2} + 1},\ldots,k_n$} \\ 0 & \text{else} \end{cases} \end{equation*}$$

$|K|$ must be even for strings generated by $L$, being the concatenation of two equally long strings. Strings with odd length can thus be immediately identified as random and thus uninteresting.

Adding $1$ to $s$, the probability that a bit in the first half changes is equal to the probability that all bits in the second half are $1$. For $D$ to output $0$ on a string generated by $L$, exactly that case must occur as the second half is cut off and ignored. $$\begin{equation*} P(\text{bit $i$ flipped with $i>\frac{n}{2}$}) = \frac{1}{2^{\frac{n}{2}}}, \end{equation*}$$ because the lower $\frac{n}{2}$ bits must be $1$.

Hence $$\begin{equation*} P(D(G(s)) = 1) = 1 - P(D(G(s)) = 0) = 1 - \frac{1}{2^\frac{n}{2}} \end{equation*}$$

The probability that in a uniformly random bistring $r$ the upper and lower half are identical (which leads to an erroneous output $D(r)$) is the ratio between the number of possible bitrings with equal halves and all possible bistrings. For half a string, there are $2^{\frac{n}{2}}$ possibilities wo this is also the number of possibilities for strings with equal halves, with $2^n$ total strings.

$$\begin{equation*} P(D(r) = 1) = \frac{2^{\frac{n}{2}}}{2^n} = 2^{-\frac{n}{2}} = \frac{1}{2^\frac{n}{2}} \end{equation*}$$

Furthermore $$\begin{equation*} \left\lvert P(D(G(s)) = 1) - P(D(r) = 1) \right\rvert = \left\lvert1 - \frac{1}{2^\frac{n}{2}} - \frac{1}{2^\frac{n}{2}}\right\rvert = 1 - \frac{2}{2^{\frac{n}{2}}} = 1 - \frac{1}{2^{\frac{n}{2} - 1}} \end{equation*}$$

This is non-negligible and increases with increasing $n$. $L$ is therefore not necessarily pseudorandom.

$\endgroup$
  • 1
    $\begingroup$ A beautiful proof! $\endgroup$ – user1767774 Nov 16 '17 at 22:37
  • $\begingroup$ @oarfish I don't really understand... Isn't the output of function $L$ behaves just like a pad generated in a CTR cipher (except for $IV$ does not participate in pad directly, but this is another question)? And I also believe that when $s+1$, the probability of "the first half does not change" is equal to the probability of "all bits in the second half are $1$". Or the probability "a bit in the first half changes" is equal to ${}_{\frac{n}{2}}C_1/2^{\frac{n}{2}}$. $\endgroup$ – wangkaibule Jan 5 '18 at 14:34

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.