  Local pseudorandom generators are a class of fundamental cryptographic
primitives having very broad applications in theoretical cryptography.
Following Couteau et al.'s work in 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 Couteau et 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 $2^{61}$,
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
Couteau et al.'s work in ASIACRYPT 2018 aiming for 80-bit (128-bit) security
levels can be solved in about $2^{58}$ ($2^{78}$) operations. We suggest new
parameters for achieving 80-bit (128-bit) security with respect to our attacks.
We also extend the attack to other promising predicates and investigate their
resistance.
