# 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. – fkraiem 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. – Juan Miguel Arrazola Jul 20 '16 at 12:23
• What is "information-theoretic hardness"? Statistical distance? – fkraiem 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? – poncho Jul 20 '16 at 13:22
• Information-theoretic hardness means that even with unlimited computational power, the problem is still hard to solve. – Juan Miguel Arrazola 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? – Juan Miguel Arrazola 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. – Kevin Jul 22 '16 at 3:27