Ximing Fu
Harbin Institute of Technology, Shenzhen Pengcheng Laboratory, Shenzhen

Mo Li
The Chinese University of Hong Kong, Shenzhen

Shihan Lyu
The Chinese University of Hong Kong, Shenzhen

Chuanyi Liu
Harbin Institute of Technology, Shenzhen Pengcheng Laboratory, Shenzhen

Keywords: Goldreich's PRGs, XOR-THR predicates, noisy equations, FiLIP, cryptanalysis

Abstract

Goldreich's pseudorandom generators (PRGs) with constant locality admit highly parallel implementations, yet the concrete security of instantiations based on the $\xor\text{-}\thr$ predicate has remained unclear.

In this work, we present novel seed recovery attacks on Goldreich's PRGs instantiated on \(\xor\text{-}\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 $2^{n(1-\log_2{(1 + \frac{2s}{\sqrt{2\pi (b-s)}})})}$ calls to Gaussian elimination when the input length of the $\thr$ predicate $b\geq (n-s)^{1/s}+s-1$ with small stretch $s$.

Applying our attack to the \(\xor\text{-}\maj\) challenges in STOC 2016 yields complexity \(2^{\,n\!\left(1-\log_{2}\!\left(1+\sqrt{\frac{s}{18\pi}}\right)\right)} \le 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 hours, 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_{100}\text{-}\thr_{11,22}\text{-}\thr_{11,22}\) is broken in about \(2^{59}\) calls to Gaussian elimination over 357 variables despite a 397-bit key and a claimed 80-bit security level.