Paper 2026/2156

Cryptanalysis of Goldreich's PRGs with MAJ–XOR Predicates

Abstract

Goldreich's pseudorandom generators (PRGs) expand a secret seed by evaluating a fixed low-locality predicate on random subsets of its bits. We study the concrete and asymptotic security of constructions whose local predicate combines majority with XOR. We introduce Deterministic Pooled Recovery (DPR), which guesses a set of seed positions and pools the outputs whose majority inputs are forced by the guess. The selected outputs yield noiseless sparse linear equations. For the proposed \(\operatorname{MAJ}_7\oplus\operatorname{XOR}_4\) challenge published in ToSC 2025, with seed length \(n=1024\) and output length \(m=n^2\), DPR has an estimated recovery cost of \(2^{109.71}\) operations using \(\omega=2.38\) for the linear-algebra exponent. This is below the claimed 128-bit security level. We also refine the common-bias analysis by evaluating its advantage at each fixed seed weight. This viewpoint motivates Bias-Amplified Pooled Recovery (BAPR), which uses partial majority bias to construct pooled noisy linear systems. For \(m=n^s\) with fixed \(s>1\), odd majority locality \(a\in\omega(1)\cap O(\log n)\), and fixed XOR locality \(b\ge3\), we prove that BAPR admits a worst-case \(2^{o(n)}\)-time implementation that recovers any fixed seed with high probability. This rules out exponential security in this intermediate-locality regime. In addition, we identify exploitable affine structure and residue constraints in proposed alternative predicates.