UC Berkeley

In the first part of this thesis, we consider the construction of unconditional pseudorandom generators whose outputs look random to depth-2 boolean circuits. We prove the existence of a $poly(n,m)$-time computable pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables and $m$ terms, and has seed length $O(log^2 nm cdot loglog nm)$. Previously, the best pseudorandom generator for depth-2 circuits had seed length $O(log^3 nm)$, and was due to Bazzi (FOCS 2007).

It follows from our proof that a $1/m^{tilde O(log mn)}$-biased distribution $1/poly(nm)$-fools DNFs with $m$ terms and $n$ variables. For inverse polynomial distinguishing probability this is nearly tight because we show that for every $m,delta$ there is a $1/m^{Omega(log 1/delta)}$-biased distribution $X$ and a DNF $phi$ with $m$ terms such that $phi$ is not $delta$-fooled by $X$.

For the case of {em read-once} DNFs, we show that seed length $O(log mn cdot log 1/delta)$ suffices, which is an improvement for large $delta$.

It also follows from our proof that a $1/m^{O(log 1/delta)}$-biased distribution $delta$-fools all read-once DNFs with $m$ terms. We show that this result too is nearly tight, by constructing a $1/m^{tilde Omega(log 1/delta)}$-biased distribution that does not $delta$-fool a certain $m$-term read-once DNF.

In the second part of this thesis, we consider Goldreich's (ECCC 2000) proposed candidate one-way function construction which is parameterized by the choice of a small predicate (over $d$ variables) and of a bipartite expanding graph of right-degree $d$. The function is computed by labeling the $n$ vertices on the left with the bits of the input, labeling each of the $n$ vertices on the right with the value of the predicate applied to the neighbors, and outputting the $n$-bit string of labels of the vertices on the right.

Inverting Goldreich's one-way function is equivalent to finding a solution for a certain constraint satisfaction problem with a ``planted solution.'' Such a problem easily reduces to SAT, and so the use of SAT solvers constitutes a natural class of attacks.

We initiate a rigorous study of the limitations of backtracking attacks against Goldreich's function. Results by Alekhnovich, Hirsch and Itsykson imply that Goldreich's function is secure against ``myopic'' backtracking algorithms (an interesting subclass) if the 3-ary parity predicate $P(x_1,x_2,x_3) = x_1 oplus x_2 oplus x_3$ is used. However, the construction must use non-linear predicates; otherwise inversion succumbs to a trivial attack via Gaussian elimination.

We generalize the work of Alekhnovich et al. to handle more general classes of predicates, and we present a lower bound for the construction that uses random predicates or predicates of the form ( P (x_1,ldots,x_d) = x_1 oplus x_2 oplus cdots oplus x_{d-h} oplus Q(x_{d-h+1}, ldots, x_d), )

and a random graph.

We also study how far Goldreich's function is from an injective function. We give upper bounds of the form $2^{2^{-Omega(d)} n}$ on the average size of preimages of Goldreich's function when the graph $G$ is random,

and the predicate $P$ is random or $P = x_1 oplus x_2 oplus cdots oplus x_{d-h} oplus Q(x_{d-h+1}, ldots, x_d)$ for $d-h=Omega(d)$.