On the One-Way Function Candidate Proposed by Goldreich
James Cook, Omid Etesami, Rachel Miller, Luca Trevisan · ACM Transactions on Computation Theory · 2014
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 random or depends linearly 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 preceding 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 to 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.