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$
4
  • $\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
    Commented Nov 20, 2015 at 12:13
  • $\begingroup$ I am not sure what the difference is, but I would label it PRNG. $\endgroup$
    – oarfish
    Commented Nov 20, 2015 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
    Commented Nov 20, 2015 at 12:31
  • $\begingroup$ You probably want the probabilities of individual bits being 0 or 1 to be equal, a uniform distribution at the bit level. But the construction L(s) := G(s) || G(s+1) gives a 1 in the kth place iff either the same place in G(s) gets a 1. If the samples G(s) and G(s+1) were uncorrelated, then the probability of a 1 in any specific position of L(s) would be 0.75 rather than 0.5. Whether the bias violates your meaning of PRNG, I don't really know (since you do not give your definition). $\endgroup$
    – hardmath
    Commented Nov 5, 2023 at 20:51

4 Answers 4

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$
5
  • $\begingroup$ Can you give a source for why it is known? $\endgroup$
    – oarfish
    Commented Nov 20, 2015 at 13:13
  • 1
    $\begingroup$ Any good cryptography textbook (e.g., Goldreich or Katz-Lindell). $\endgroup$
    – fkraiem
    Commented Nov 20, 2015 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$ Commented Jan 6, 2018 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
    Commented Jan 6, 2018 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
    Commented Jan 6, 2018 at 3:06
4
$\begingroup$

I would like to improve upon @fkraiem answer (i.e. give a simpler construction):

you must exhibit a pseudorandom generator G such that L is not a pseudorandom generator.

Take any pseudorandom number generator $PRG : \{0,1\}^{n-1} \rightarrow \{0,1\}^{l(n)}$. Now define $G : \{0,1\}^n \rightarrow \{0,1\}^{l(n)}$ to be $G(x_1 | x_2 ... | x_n) = PRG(x_1 | x_2 ... | x_{n-1})$.

I.e. $G$ ignores the last input bit and passes the truncated key to $PRG$.

$G$ is a pseudorandom number generator but $L = G(s)|G(s+1)$ is not:

Let's construct a distinguisher $D$ that given a number $x = x_1 | x_2 | ... | x_{2l(n)}$ tells whether it was sampled uniformly at random, or whether it was generated from $L$:

# our distinguisher
fun D(x):
    if the first half of x equals to the second half of x:
        return 1
    else
        return 0

If $x = r$ is a truly random number, then $\Pr[D(r) = 1] = 2^{-l(n)}$

If $x = L(s)$ was generated using $L$ from a random key $s = s_1|s_2|...|s_n$, then at least half of the time G(s) is identical to G(s+1) (because half of the time the last bit $s_n = 0$) and so at least half of the time the distinguisher $D$ outputs 1, thus the difference

$|\Pr[D(G(s)) = 1] - \Pr[D(r) = 1]| \geq \frac{1}{2} - 2^{-l(n)}$ is not negligible.

$\endgroup$
1
  • 1
    $\begingroup$ You might add a note about the endianness you're assuming for this to work. $\endgroup$
    – Maeher
    Commented Mar 20, 2021 at 14:11
1
$\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$
2
  • 1
    $\begingroup$ A beautiful proof! $\endgroup$ Commented Nov 16, 2017 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$ Commented Jan 5, 2018 at 14:34
0
$\begingroup$

Here's yet another proof. The idea is to use $L$ against itself! Suppose $L(s)$ is PRG, so we can use it in place of $G$, which will lead to: $$H(s)=L(s)\|L(s+1)=G(s)\|G(s+1)\|G(s+1)\|G(s+2)$$ Since the second and third parts are the same, a distinguisher can be made easily and $H$ won't be PRG and by contradiction we get that $L$ is not PRG.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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