Pseudorandomness from Shrinkage

by Russell Impagliazzo, Raghu Meka, and David Zuckerman

Oded's comments

I am not going to discuss the results and/or constructions, but rather one idea that underlies them. I am also going to use this idea to present a result that may not be explicitly stated in the paper, but is definitely implicit in it (and known to the authors).

This result refers to the possible sensitivity of some PRGs (pseudorandom generators) to the order in which their output bits are presented (or inspected). Needless to say, this refers to PRGs that fool distinguishers that cannot permute the tested string (for free), and the canonical example is that of space-bounded machines with on-line access to their input. Actually, one typically considers non-uniform space-bounded machines, which are viewed as layered automata with $2^s$ states per layer, where $s$ is the space bound (cf., e.g., Sec 8.4 in my Complexity book). Here, I will consider the case that $s$ is a constant, and two classical PRGs: the ones of Nisan and of Nisan-Zuckerman.

While Nisan's "space fooling" PRG is sensitive to the order in which its output bits are presented (or inspected), it turns out that the Nisan-Zuckerman "space fooling" PRG is insensitive to this order, where both statements refer to fooling non-uniform constant-space distinguishers. Indeed, the sensitivity of Nisan's PRG to reordering of its output bits is quite extreme in the sense that it is demonstrated with respect to constant-space distinguishers, but the insensitivity of Nisan-Zuckerman's PRG comes at a cost that is exponential in the space bound of the distinguishers being fooled (and is thus stated here only for constant space).

Regarding the sensitivity of Nisan's PRG, see Yoav Tzur's Master Thesis (i.e., Cor. 3.18), which shows that that one can distinguish in (non-uniform) constant-space between eight ($n$-bit long) blocks in Nisan's PRG (when these bits are presented in an adequate order) and a uniformly selected string of the same length (i.e., $8n$). [Recall that Nisan's PRG uses a seed of length $O(n^2)$ to generate an output of length $exp(n)$.] Specifically, the attack refers to the case that the hashing functions are implemented as affine transformations over the field $GF(2^n)$. In general, Yoav's thesis contains many interesting observations regarding candidate PRGs that are related to $GF(2^n)$ polynomials.

Regarding the insensitivity of the Nisan-Zuckerman PRG, recall that this PRG uses a seeded extractor $E:\{0,1\}^{n+d}\to\{0,1\}^m$ and transforms a seed $(X,Y_1,...,Y_t)\in\{0,1\}^{n+td}$ to the output $(E(X,Y_1),...,E(X,Y_t))\in\{0,1\}^{tm}$, where (say) $d=(\log n)^2$ and $n=t=m$ (so that we stretch $\tildeO(m)$ bits to $m^2$ bits). Clearly, the order in which these $t$ blocks are presented is immaterial, but the point here is that the PRG's fooling power (w.r.t constant-space non-uniform automata) is preserved under any permutation of the $tm$ output bits. Specifically, we shall consider distinguishers that are layered automata with $W=O(1)$ states per layer (i.e., width $W$) that read the $tm$ output bits in an arbitrary fixed order, and apply the ideas of the current paper [Impagliazzo, Meka, and Zuckerman] in the analysis.

The proof uses a hybrid argument, and shows that for every $i$, the hybrid distributions $H_i=(U_{(i-1)m},E(X,Y_i),...,E(X,Y_t))$ and $H_{i+1}$ are indistinguishable. Note that the hybrids are presented above in a "canonical order" which is not necessarily the order in which the automata inspects the bits. Now, suppose (towards the contradiction) that $D$ is automata (of width $W$) that distinguishes $H_i$ from $H_{i+1}$ with gap $\e>2^{-m}$, Consider all possible fixing of the values of the bits of the first $i-1$ blocks and the last $t-i$ blocks, and denote such a generic fixing by $f$. This fixing $f$ can be used to simplify $D$ into a automata $D'=D_f$ that only reads the $m$ bits of the $i$th block, and $D_f$ has width $W$. Note that the number of possible $D_f$'s is $W^{2Wm} = 2^{(c-1)m}$, for a suitable constant $c$ (i.e., $c = 1+ 2W\log_2 W$). Now, partition all possible fixings $f$ according to the description of the corresponding $D_f$ (i.e., $f_1$ and $f_2$ are in the same set if $D_{f_1}=D_{f_2}$), and note that there exists a set of density at least $2^{-(c-1)m}\e>2^{-cm}$ for which $D'=D_f$ preserves the distinguishing gap of $D$. Now consider the uniform distribution on this set (i.e., select $f$ uniformly such that $D_f=D'$), and note that this conditions both $X$ and $Y_{i+1},...,Y_t$ (but leaves $Y_i$ totally undetermined). Furthermore, under this conditioning, $X$ has min-entropy at least $n-cm \geq 2m$, where we assume $n\geq (c+2)m$. But if the extractor is good enough, then $D'$ cannot possibly distinguish $E(X,Y_i)$ from $U_m$, in contradiction to the hypothesis.

Note that the argument extends to the case that the automata may inspect each input bit several times, but this requires a different setting of the parameters. Specifically, for $n=t=O(km)$, we get a PRG that fools width $W$ automata that inspect each input bit up to $k=O(1)$ times, since in such a case $D'$ has description length $\log_2(W^{2Wkm})=O(km)$.

Also note that the "reordering tolerance" does not come for free. When the order is canonical (as in the Nisan-Zuckerman paper), the entropy loss is captured by the state at the current layer, and is thus $\log_2 W$. Here, when the order is arbitrary, the entropy loss is the description length of the entire automata; that is, $\log_2 W^{2Wm} = \tildeO(Wm)$.

Comment: Reordering tolerance w.r.t constant-space distinguishers is also a feature of the PRG of [Bogdanov, Papakonstantinou, and Wan, FOCS'11], which has linear stretch.

Regarding multiple-passes (but no reordering), the following observation was made by Or Meir and myself. Any PRG that fools space $ts$ with gap $\exp(-ts) \e$ can fool a $t$-pass space $s$ with gap $\e$, where in both cases the space-bounded distinguisher reads the input in the same fixed order. This observation can be proved by having $2^{(t-1)s}$ different single-pass automata each emulate the computation of the $t$-pass automata conditioned on the states that it reached after each of the $t-1$ first passes.

The original abstract

See ECCC TR12-057.

Back to list of Oded's choices.