3
$\begingroup$

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$?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ 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. $\endgroup$
    – fkraiem
    Jul 20, 2016 at 11:00
  • $\begingroup$ 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. $\endgroup$
    – Juan Miguel Arrazola
    Jul 20, 2016 at 12:23
  • $\begingroup$ What is "information-theoretic hardness"? Statistical distance? $\endgroup$
    – fkraiem
    Jul 20, 2016 at 12:24
  • 1
    $\begingroup$ 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? $\endgroup$
    – poncho
    Jul 20, 2016 at 13:22
  • $\begingroup$ Information-theoretic hardness means that even with unlimited computational power, the problem is still hard to solve. $\endgroup$
    – Juan Miguel Arrazola
    Jul 21, 2016 at 2:37

1 Answer 1

Reset to default
3
$\begingroup$

Usually what you call "information theoretic hardness" is denoted as statistical indistinguishability. And it is pretty much black and white only: Two distributions are distinguishable or not.

When you ask "how much harder", you already drift into the area of computational indistinguishability. There are plenty of ressources for that keyword, including most books about introduction into cryptography.

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)"

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Juan Miguel Arrazola
    Jul 22, 2016 at 2:54
  • $\begingroup$ @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. $\endgroup$
    – Kevin
    Jul 22, 2016 at 3:27

Your Answer

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

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