 Main
Pseudorandomness against Depth2 Circuits and Analysis of Goldreich's Candidate OneWay Function
 Author(s): Etesami, Seyed Omid
 Advisor(s): Trevisan, Luca
 et al.
Abstract
In the first part of this thesis, we consider the construction of unconditional pseudorandom generators whose outputs look random to depth2 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 depth2 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 readonce} 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 readonce 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 readonce DNF.
In the second part of this thesis, we consider Goldreich's (ECCC 2000) proposed candidate oneway function construction which is parameterized by the choice of a small predicate (over $d$ variables) and of a bipartite expanding graph of rightdegree $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 oneway 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 3ary parity predicate $P(x_1,x_2,x_3) = x_1 oplus x_2 oplus x_3$ is used. However, the construction must use nonlinear 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_{dh} oplus Q(x_{dh+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_{dh} oplus Q(x_{dh+1}, ldots, x_d)$ for $dh=Omega(d)$.
Main Content
Enter the password to open this PDF file:













