<p>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.</p>

<p>O. Goldreich and A. Wigderson. <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/ODED/UBPP/RANDOM/proc.ps">On pseudorandomness with respect to deterministic observers</a></p>

<p>O. Goldreich. <a href="http://www.wisdom.weizmann.ac.il/~oded/PDF/bpp.pdf">In a world of P=BPP</a></p>

<p>R. Williams. <a href="http://www.stanford.edu/~rrwill/nexp-v-bpp.pdf">Towards NEXP versus BPP?</a></p>

CC BY-SA 3.0
2014-10-30T17:26:16.310Z
2014-10-30T17:26:16.310Z
Ryan Williams
<p>I've seen pseudorandom generators defined for nonuniform efficient adversaries, or uniform probabilistic efficient adversaries.  (For example, a monograph <em>Pseudorandomness</em> by Vadhan (<a href="http://people.seas.harvard.edu/~salil/pseudorandomness/" rel="nofollow">here's its draft</a> does that.)</p>

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

<p>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.</p>

CC BY-SA 3.0
2014-10-29T06:33:56.613Z
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?
Kaveh
CC BY-SA 3.0
2014-10-29T08:03:06.310Z
@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.
Pteromys
CC BY-SA 3.0
2014-10-29T13:41:28.567Z
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.
usul
CC BY-SA 3.0
2014-10-29T14:47:15.737Z
@Ricky, yes, and that last nonuniform in my comment should have been uniform.
Kaveh
CC BY-SA 3.0
2014-10-29T14:50:35.543Z
@Pteromys, I don't think the arguments for the uniform versions are significantly simpler than the arguments for nonuniform versions. If you have a good a good counterexample to this please add it to the question as a motivation for it. :)
Kaveh
<cc.complexity-theory><reference-request><pseudorandomness><pseudorandom-generators>
Pseudorandom generators indistinguishable by uniform deterministic adversaries
Pteromys
# Pseudorandom generators indistinguishable by uniform deterministic adversaries

(Asked by: username_0 on 2014-10-29)

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](http://people.seas.harvard.edu/~salil/pseudorandomness/) 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.

**Tags:** cc.complexity-theory, reference-request, pseudorandomness, pseudorandom-generators
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_2**: 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.  
> **username_1**: @Ricky, yes, and that last nonuniform in my comment should have been uniform.  
> **username_1**: @Pteromys, I don't think the arguments for the uniform versions are significantly simpler than the arguments for nonuniform versions. If you have a good a good counterexample to this please add it to the question as a motivation for it. :)  

---

## 1 answers

### Answer by username_3 on 2014-10-30. Score: 7 | Accepted answer

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](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/ODED/UBPP/RANDOM/proc.ps)

O. Goldreich. [In a world of P=BPP](http://www.wisdom.weizmann.ac.il/~oded/PDF/bpp.pdf)

R. Williams. [Towards NEXP versus BPP?](http://www.stanford.edu/~rrwill/nexp-v-bpp.pdf)


---

