6
$\begingroup$

I've seen pseudorandom generators defined for nonuniform efficient adversaries, or uniform probabilistic efficient adversaries. (For example, a monograph Pseudorandomness by Vadhan (here's its draft does that.)

I believe that it's natural to think about pseudorandom generators indistinguishable by uniform deterministic efficient adversaries. Has that notion studied before? Does it have any significance to some degree?

EDIT: I was mistaken in that Vadhan defined pseudorandomness against uniform probabilistic adversaries: he did define indistinguishability by uniform probabilistic algorithms, but he neither defined, nor stated facts about, the corresponding notion of pseudorandomness. My interest mostly concerned with uniform adversaries and my original question was about deterministic vs. probabilistic.

Improve this question
$\endgroup$
6
  • $\begingroup$ Any PRNG which is secure against nouniform adversaries is secure against corresponding uniform adversaries. So if you cannot do much (if anything) extra when restricting to nonuniform adversaries (which as far as I know is the case) why go with the weaker model of security? $\endgroup$
    – Kaveh
    Oct 29, 2014 at 6:33
  • $\begingroup$ @Kaveh : $\:$ More generally, any "PRNG which is secure against" probabilistic "adversaries is secure against corresponding" uniform deterministic adversaries. $\;\;\;\;$ $\endgroup$
    – user6973
    Oct 29, 2014 at 7:53
  • $\begingroup$ @Kaveh Why? Because it may be easier to reason about its property (like its existence, but not limited to this) than the probabilistic counterpart all the more for its simplicity and weakness, for example. I know the deterministic version makes practitioners no happier. $\endgroup$
    – Pteromys
    Oct 29, 2014 at 8:03
  • 4
    $\begingroup$ Don't know if it's been studied. But if research there is rare, it might be because the uniform adversary model, whether probabilistic or no, seems not very useful for derandomization. Note Vadhan does not even write the definition of PRGs against uniform adversaries (does he state any results for such PRGs?). The nonuniform adversary is much more obviously useful for derandomization; the proof of Claim 7.6 illustrates why. $\endgroup$
    – usul
    Oct 29, 2014 at 13:41
  • $\begingroup$ @Ricky, yes, and that last nonuniform in my comment should have been uniform. $\endgroup$
    – Kaveh
    Oct 29, 2014 at 14:47

1 Answer 1

Reset to default
7
$\begingroup$

Yes, this notion has been studied. One interesting aspect is that the two notions of pseudorandomness known to be equivalent under the usual adversaries, "next bit predictability" and "indistinguishability", do not seem to be equivalent for deterministic adversaries. (If they were, we would have complexity class separations.) Here are three references; I'm sure there are more.

O. Goldreich and A. Wigderson. On pseudorandomness with respect to deterministic observers

O. Goldreich. In a world of P=BPP

R. Williams. Towards NEXP versus BPP?

Improve this answer
$\endgroup$

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.