Revisiting the Concrete Security of Goldreich’s Pseudorandom Generator
Jing Yang, Qian Guo, Thomas P. Johansson, Michael Lentmaier · IEEE Transactions on Information Theory · 2021
Local pseudorandom generators are a class of fundamental cryptographic primitives having very broad applications in theoretical cryptography. Following Couteauet al.’swork at ASIACRYPT 2018, this paper further studies the concrete security of one important class of local pseudorandom generators, i.e., Goldreich’s pseudorandom generators. Our first attack is of the guess-and-determine type. Our result significantly improves the state-of-the-art algorithm proposed by Couteauet al., in terms of both asymptotic and concrete complexity, and breaks all the challenge parameters they proposed. For instance, for a parameter set suggested for 128 bits of security, we could solve the instance faster by a factor of about 277, thereby destroying the claimed security completely. Our second attack further exploits the extremely sparse structure of the predicate$P_{5}$and combines ideas from iterative decoding. This novel attack, named guess-and-decode, substantially improves the guess-and-determine approaches for cryptographic-relevant parameters. All the challenge parameter sets proposed in Couteauet al.’swork in ASIACRYPT 2018 aiming for 80-bit (128-bit) security levels can be solved in about 258(278) operations. We suggest new parameters for achieving 80-bit (128-bit) security with respect to our attacks. We also extend the attacks to other promising predicates and investigate their resistance.