 Main
Pseudorandomness against Depth2 Circuits and Analysis of Goldreich's Candidate OneWay Function
 Etesami, Seyed Omid
 Advisor(s): Trevisan, Luca
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:













