Welcome to the resource topic for 2024/1594
Title:
Bit-fixing Correlation Attacks on Goldreich’s Pseudorandom Generators
Authors: Ximing Fu, Mo Li, Shihan Lyu, Chuanyi Liu
Abstract:We introduce a powerful attack, termed the bit-fixing correlation attack, on Goldreich’s pseudorandom generators (PRGs), specifically focusing on those based on the \mathsf{XOR}\text{-}\mathsf{THR} predicate. By exploiting the bit-fixing correlation property, we derive correlation equations with high bias by fixing certain bits. Utilizing two solvers to handle these high-bias correlation equations, we present inverse attacks on \mathsf{XOR}\text{-}\mathsf{THR} based PRGs within the complexity class \mathsf{NC}^{0}.
We efficiently attack the \mathsf{XOR}\text{-}\mathsf{MAJ} challenges (STOC 2016), demonstrating that the \mathsf{XOR}\text{-}\mathsf{MAJ} predicate fails to be s-pseudorandom with n-bit security even for a stretch factor s = 1, where n is the size of the secret seed. For instance, a challenge of n=42 and s = 1 can be broken using approximately 2^{28} calls to Gaussian elimination. We extend our attack to an instance used in constructing silent Oblivious Transfer (OT) protocols (Eurocrypt 2024), with n=256. This attack can be realized with approximately 2^{29} calls to Gaussian elimination, and we have implemented this attack on a cluster of 32 CPU cores, successfully recovering the secret seed in 5.5 hours. Furthermore, we extend our results to general Piecewise Symmetric Predicates of the form \mathsf{XOR}\text{-}\mathsf{X}, showing that \mathsf{XOR}\text{-}\mathsf{MAJ} is far from well designed predicate against bit-fixing correlation attack.
With marginal modification, our attack can also be adapted to the FiLIP cipher instantiated with \mathsf{THR}-related predicates, making it effective against most FiLIP instances. For example, the FiLIP cipher instantiated on \mathsf{XOR} \text{-}\mathsf{THR} with key size 982 can be broken using approximately 2^{51} calls to Gaussian elimination.
Based on these findings, we show that the traditional security assumptions for Goldreich’s PRGs—namely, (a) \Omega(s)-resilience and (b) algebraic immunity—are insufficient to guarantee pseudorandomness or one-wayness.
ePrint: https://eprint.iacr.org/2024/1594
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .