Paper 2018/1162

On the Concrete Security of Goldreich’s Pseudorandom Generator

Geoffroy Couteau, Aurélien Dupin, Pierrick Méaux, Mélissa Rossi, and Yann Rotella

Abstract

Local pseudorandom generators allow to expand a short random string into a long pseudo-random string, such that each output bit depends on a constant number d of input bits. Due to its extreme efficiency features, this intriguing primitive enjoys a wide variety of applications in cryptography and complexity. In the polynomial regime, where the seed is of size n and the output of size n^s for s > 1, the only known solution, commonly known as Goldreich's PRG, proceeds by applying a simple d-ary predicate to public random size-d subsets of the bits of the seed. While the security of Goldreich's PRG has been thoroughly investigated, with a variety of results deriving provable security guarantees against class of attacks in some parameter regimes and necessary criteria to be satisfied by the underlying predicate, little is known about its concrete security and efficiency. Motivated by its numerous theoretical applications and the hope of getting practical instantiations for some of them, we initiate a study of the concrete security of Goldreich's PRG, and evaluate its resistance to cryptanalytic attacks. Along the way, we develop a new guess-and-determine-style attack, and identify new criteria which refine existing criteria and capture the security guarantees of candidate local PRGs in a more fine-grained way.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in ASIACRYPT 2018
Keywords
Pseudorandom generatorsAlgebraic attacksGuess-and-DetermineGröbner basis
Contact author(s)
geoffroy couteau @ kit edu
dupin aurelien @ gmail com
pierrick meaux @ uclouvain be
melissa rossi @ ens fr
yann rotella @ inria fr
History
2019-01-31: last of 2 revisions
2018-12-03: received
See all versions
Short URL
https://ia.cr/2018/1162
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1162,
      author = {Geoffroy Couteau and Aurélien Dupin and Pierrick Méaux and Mélissa Rossi and Yann Rotella},
      title = {On the Concrete Security of Goldreich’s Pseudorandom Generator},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1162},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1162}},
      url = {https://eprint.iacr.org/2018/1162}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.