Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets
This work addresses a theoretical gap in cryptography by extending analysis to non-binary alphabets, though it is incremental as it builds on prior binary-focused techniques.
The paper tackles the problem of analyzing linear programming relaxation attacks on non-binary generalizations of Goldreich's pseudorandom generators, deriving an exact threshold for when the attack can determine many input variables based on parameters like output size and known inputs.
Goldreich suggested candidates of one-way functions and pseudorandom generators included in $\mathsf{NC}^0$. It is known that randomly generated Goldreich's 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 Goldreich's generator and derives the tight threshold for linear programming relaxation attack using local marginal polytope for randomly generated Goldreich's generators. We assume that $u(n)\in ω(1)\cap o(n)$ input variables are known. In that case, we show that when $r\ge 3$, there is an exact threshold $μ_\mathrm{c}(k,r):=\binom{k}{r}^{-1}\frac{(r-2)^{r-2}}{r(r-1)^{r-1}}$ such that for $m=μ\frac{n^{r-1}}{u(n)^{r-2}}$, the LP relaxation can determine linearly many input variables of Goldreich's generator if $μ>μ_\mathrm{c}(k,r)$, and that the LP relaxation cannot determine $\frac1{r-2} u(n)$ input variables of Goldreich's generator if $μ<μ_\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.