5
$\begingroup$

Is it possible to have a pseudorandom generator that extends its output by 1 bit by simply appending the exclusive-or of all the previous bits?

I know the output of a pseudorandom generator is indistinguishable from random, so would the appended bit still retain its pseudorandom property? Or is this not pseudorandom because the last bit is deterministic?

$\endgroup$
8
$\begingroup$

This allows for an easy distinguishing attack: Let $R\colon\;\{0,1\}^n\to\{0,1\}^m$ denote a pseudo-random generator, that is, if $x$ and $y$ are uniformly distributed random variables in $\{0,1\}^n$ resp. $\{0,1\}^m$, there is no polynomial-time algorithm that distinguishes $R(x)$ from $y$ with non-negligible probability.

Let $R'\colon\;\{0,1\}^n\to\{0,1\}^{m+1}$ denote the generator whose output is extended as specified in the question. An attacker, given a black box $z$ that contains either $R'(x)$ (for $x$ uniformly random in $\{0,1\}^n$) or $y$ (uniformly random in $\{0,1\}^{m+1}$), may then calculate the parity (exclusive or) of $z$'s first $m$ bits and compare it to the last bit of $z$. If they match, the attacker guesses that $z$ is $R'(x)$, else he guesses that $z$ is $y$.

It is fairly obvious that, using this strategy, the attacker always guesses correctly when given $R'(x)$. In the other case, when given $y$, the strategy has a success probability of exactly $\frac12$, since the last bit of a random bit string is also random and may thus with equal probabilities either match (in which case the attacker guesses wrong) or mismatch (in which case the attacker guesses right) the parity.

Therefore, the attacker has a success probability of $$\frac12\cdot1+\frac12\cdot\frac12=\frac34$$ in distinguishing $R'$ from random, which is non-neglibly greater than $\frac12$.


A less direct argument is: If the extension described in the question was possible, one could iterate the construction multiple times without losing the pseudo-randomness property. However, after the first such extension, the parity of the output is always zero, hence all further appended bits are zero. Clearly, a generator whose output always ends in a string of zeroes is not pseudo-random.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Alternatively, $\;\;\;$ "$z$'s first $m$ bits" $\: \mapsto \:$ "$z$" $\;\;$ and $\;\;$ "the last bit of $z$" $\: \mapsto \:$ "$0$" $\;\;$. $\;\;\;\;\;\;\;$ $\endgroup$ – user991 Dec 16 '14 at 2:39
  • $\begingroup$ @RickyDemer: Thanks; it seems this only came to my mind while writing the last paragraph. I think the current description is a bit clearer, as one may not immediately realize that appending a parity bit, which is of course just a disguised CRC with polynomial $X+1$, yields a bit string of parity zero. Besides that, applying your simplification might hide that this attack is not at all specific to parity, but may be applied to any function that maps $\{0,1\}^m$ to $\{0,1\}$. For these reasons, I'll keep the answer as is for now. $\endgroup$ – yyyyyyy Dec 16 '14 at 19:40
4
$\begingroup$

If you define pseudorandom as (computationally) indistinguishable from random, then your proposal breaks the pseudorandom property. Here is why, given all the previous bits, can you predict (with significantly better than 0.5 probability) what the next bit will be? The answer is yes, you can predict it 100% of the time.

| improve this answer | |
$\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.