Revisiting the Concrete Security of Goldreich’s Pseudorandom Generator

DOI10.1109/TIT.2021.3128315MaRDI QIDQ5030366zbMATH OpenOpenAlexFDO

Authors Jing Yang, Qian Guo, Thomas Johansson, M. Lentmaier

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.02668

zbMATH Keywords

guess-and-decodelocal pseudorandom generators

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Cryptography (94A60)

Abstract: 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.

Cited in

(6)

• MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications
• Compressing unit-vector correlations via sparse pseudorandom generators
• Fast public-key silent OT and more from constrained Naor-Reingold
• On the concrete security of Goldreich's pseudorandom generator
• On the algebraic immunity -- resiliency trade-off, implications for Goldreich's pseudorandom generator
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)

This page was built for publication: Revisiting the Concrete Security of Goldreich’s Pseudorandom Generator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5030366)