PRNG output with truly random noise

I am considering a situation where an adversary does not have access to the $n$-bit output string of a PRNG, but instead receives a noisy version of it, where each bit of the string is flipped with probability $p$. We assume that this noise which causes the bits to flip is truly random.

What can we say concretely about the difficulty of distinguishing this noisy PRNG output from a truly random string? Of course, for $p=0$ we recover the standard scenario for the PRNG and the problem is as hard as solving the underlying computational problem, and for $p=\frac12$ the string is truly random. But what about intermediate values of $p$? Does the distinguishing problem become significantly more difficult even if $p\ll 1$?

• If the pseudorandom generator is good, then the distinguishing problem is hard to begin with, so I'm not sure what "significantly more difficult" could mean here. Jul 20 '16 at 11:00
• Well, it becomes more difficult in an information-theoretic way. For instance, for p=0.5, the string is truly random so there is no algorithm that distinguishes from a truly random string. I am curious about this problem because it contains both computational and information-theoretic hardness to solve. Jul 20 '16 at 12:23
• What is "information-theoretic hardness"? Statistical distance? Jul 20 '16 at 12:24
• Hint: can you design a "PRNG" which is distinguishable with $p=0$, but isn't if $p$ tiny but nonzero? Can you design a "PRNG" which is distinguishable with $p$ close to (but not exactly) 0.5? Jul 20 '16 at 13:22
• Information-theoretic hardness means that even with unlimited computational power, the problem is still hard to solve. Jul 21 '16 at 2:37

So the actual answer to your question would be "If the distribution of p is distinguishable (which is the case for any $p\neq1/2$), and the distribution of the PRNG is distinguishable, then your construction is distinguishable (from a truly random distribution)"
• Yes, I am interested in computational indistinguishability. Any $p\neq 0$ should make the PRNG output even more difficult to computationally distinguish from a truly random string. Is there any meaningful way in which this can be quantified? Jul 22 '16 at 2:54
• @JuanMiguelArrazola: I imagine your PRNG is producing less than one bit of entropy per bit of output, and any $p \neq \frac{1}{2}$ is similarly producing less than one bit of entropy per bit. So then it's just a matter of figuring out how the entropy values combine. My intuition says we just take the maximum of the two values, but I'm not really sure why. Jul 22 '16 at 3:27