Attacks on Goldreich’s Pseudorandom Generators by Grouping and Solving

Goldreich’s pseudorandom generators (PRGs) with constant locality admit highly parallel implementations, yet the concrete security of instantiations based on the XOR-THR predicate has remained unclear. In this work, we present novel seed recovery attacks on Goldreich’s PRGs instantiated on XOR-THR predicates with m=n^s, where m and n are the length of output and input, respectively. By partitioning the output bits into groups according to common input bits, high-biased noisy equations can be derived for the group whose common input bits are all 1s (or all 0s). Leveraging two solvers tailored to these equations, we achieve the seed recovery attacks, which needs roughly 2n(1-log^{2(1+2s2π(b-s))}) calls to Gaussian elimination when the input length of the THR predicate b≥(n-s)^1/s+s-1 with small stretch s. Applying our attack to the XOR-MAJ challenges in STOC 2016 yields complexity 2^n1-log^21+s18π≤2^0.82n, i.e., at least a 2^0.18n speedup over exhaustive search for any stretch s>1. We also deploy our attack on an instance used in the construction of silent oblivious transfer protocols (Eurocrypt 2024) with n=256. This attack is capable of breaking the instance using approximately 2^31.3 calls to Gaussian elimination over 244 variables. We successfully implemented the attack on a cluster of 14 CPU cores, recovering the seed in 71 h, demonstrating the attack’s efficiency. Beyond PRGs, with appropriate adaptations our method extends to FiLIP stream ciphers instantiated with THR-related predicates. Our evaluation indicates that most FiLIP instances do not meet their claimed security. For instance, the configuration XOR₁₀₀-THR_11,22-THR_11,22 is broken in about 2⁵⁹ calls to Gaussian elimination over 357 variables despite a 397-bit key and a claimed 80-bit security level.