Revisiting the Concrete Security of Goldreich’s Pseudorandom Generator

DOI10.1109/TIT.2021.3128315zbMATH Open1489.94114arXiv2103.02668OpenAlexW3212914131MaRDI QIDQ5030366FDOQ5030366

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

Publication date: 17 February 2022

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

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.

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)

Cited In (6)

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

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)