We study the power of non-uniform attacks against one-wayfunctions and pseudorandom generators.

Fiat and Naor show that for every functionf:[N][N] there is an algorithm that inverts f everywhere using (ignoring lower order factors) time, space and advice at most N34 .

We show that an algorithm using time, space and advice at mostmax45N43 N exists that inverts f on at least an fraction of inputs.A lower bound of (N) also holds,making our result tight in the ``low end'' of 31N .

(Both the results of Fiat and Naor and oursare formulated as more general trade-offs between the timeand the space and advice length of the algorithm. The results quotedabove correspond to the interesting special case in which timeequals space and advice length.)

We also show that for every length-increasing generatorG:[N][2N] there is a algorithm that achieves distinguishingprobability between the output of G andthe uniform distribution and that can be implemented in polynomial (in logN) time and with advice and space O(2NlogN).Alternatively, it can be implemented as a circuitof size O(2N). We prove a lower bound of ST(2N) whereT is the time used by the algorithm and S is the amount of advice.

We prove stronger lower bounds in the {\em common random string}model, for families of one-way permutations and of pseudorandom generators.