Linear Programming Relaxations for Goldreichs Generators over Non-Binary Alphabets

Goldreich suggested candidates of one-way functions and pseudorandom generators included in $mathsf{NC}^0$. It is known that randomly generated Goldreichs generator using $(r-1)$-wise independent predicates with $n$ input variables and $m=C n^{r/2}$ output variables is not pseudorandom generator with high probability for sufficiently large constant $C$. Most of the previous works assume that the alphabet is binary and use techniques available only for the binary alphabet. In this paper, we deal with non-binary generalization of Goldreichs generator and derives the tight threshold for linear programming relaxation attack using local marginal polytope for randomly generated Goldreichs generators. We assume that $u(n)in omega(1)cap o(n)$ input variables are known. In that case, we show that when $rge 3$, there is an exact threshold $mu_mathrm{c}(k,r):=binom{k}{r}^{-1}frac{(r-2)^{r-2}}{r(r-1)^{r-1}}$ such that for $m=mufrac{n^{r-1}}{u(n)^{r-2}}$, the LP relaxation can determine linearly many input variables of Goldreichs generator if $mu>mu_mathrm{c}(k,r)$, and that the LP relaxation cannot determine $frac1{r-2} u(n)$ input variables of Goldreichs generator if $mu<mu_mathrm{c}(k,r)$. This paper uses characterization of LP solutions by combinatorial structures called stopping sets on a bipartite graph, which is related to a simple algorithm called peeling algorithm.