Goldreich [2000] proposed a candidate one-way function based on a bipartite graph of small right-degree $d$, where the vertices on the left (resp. right) represent input (resp. output) bits of the function. Each output bit is computed by evaluating a fixed $d$-ary binary predicate on the input bits adjacent to that output bit. We study this function when the predicate is either random or linearly depends on many of its input bits. We assume that the graph is a random balanced bipartite graph with right-degree $d$.
Inverting this function as a one-way function by definition means finding an element in the preimage of output of this function for a random input. We bound the expected size of this preimage.
Next, using the above bound, we prove that two restricted types of backtracking algorithms called ``myopic'' and ``drunk'' backtracking algorithms with high probability take exponential time to invert the function, even if we allow the algorithms use ``DPLL'' elimination rules. (For drunk algorithms, a similar result was proved by Itsykson [2010].)
We also ran a SAT solver on the satisfiability problem equivalent to the problem of inverting the function, and experimentally observed an exponential increase in running time as a function of the input length.
A function $f$ mapping $n$-bit strings to $m$-bit strings can be constructed from a bipartite graph with $n$ vertices on the left and $m$ vertices on the right having right-degree $d$ together with a predicate $P:\{0,1\}^d\rightarrow\{0,1\}$. The vertices on the left correspond to the bits of the input to the function and the vertices on the right correspond to the bits of the output. The value of each output bit is computed by evaluating the predicate over the input bits corresponding to its neighbors. Goldreich (ECCC 2000) conjectured that this function $f$ is one-way for $m=n$ and $d=\Theta(1)$ or $d=\Theta(\log n)$, when the vertices on the right ``expand'' and the predicate $P$ is a random non-linear predicate.
Inverting $f$ as a one-way function by definition means finding an element in the preimage $f^{-1}(f(x))$ of the image of a random input $x$ under the function $f$. We bound the expected size of this preimage when the bipartite graph is a random bipartite graph with right-degree $d$. Our result is for when the predicate $P$ is a typical random predicate or $P(x_1,\ldots,x_d)=x_1 \oplus \ldots \oplus x_{d-h} \oplus Q(x_{d-h+1}, \ldots, x_d)$ where $Q$ is an arbitrary predicate having at most $d-\Theta(d)$ variables.
Inverting the function can be seen as a constraint satisfaction problem with a ``planted solution''. One can use backtracking algorithms to find this solution. Using the bound on the size of the preimage, we prove those backtracking algorithms that are ``myopic'' and those backtracking algorithms that are ``drunk'' cannot invert the function in better than exponential time on average.
Myopic backtracking algorithms are ones in which during the first levels of the backtracking tree, the algorithm has a limited view of the image $f(x)$ for which the algorithm wants to find an element in the preimage $f^{-1}(f(x))$. Our proof for myopic backtracking algorithms builds upon the work of Alekhnovich, Hirsch, and Itsykson (2005) where they instead consider solving a system of linear equations each with three variables, that is, when $P = x_1 \oplus x_2 \oplus x_3$.
Drunk backtracking algorithms for a constraint satisfaction problem are ones in which at each point in the backtracking tree, even though the algorithm can choose any variable to fix next, the bit that is first tried for that variable has to be random.
Our proof for drunk backtracking algorithms is similar to those of Itsykson (CSR 2010) and Miller (thesis 2009).
We show that these lower bounds also hold when the backtracking algorithm is allowed to eliminate ``pure literals" and ``unit clauses" as in DPLL algorithms.
Since both being myopic and being drunk are merely theoretical restrictions that allowed us to prove lower bounds, we also performed an experimental analysis by running one of the best available SAT solvers on the SAT instance equivalent to the constraint satisfaction problem corresponding to inverting the function. The solver seemed to take exponential running time.
