Attacks on Goldreich's Pseudorandom Generators by Grouping and Solving↗ (원문, 새 창)

본문 미리보기

Goldreich's pseudorandom generators (PRGs) with constant locality admit highly parallel implementations, yet the concrete security of instantiations based on the $\xor\text{-}\thr$ predicate has remained unclear. In this work, we present novel seed recovery attacks on Goldreich's PRGs instantiated on \(\xor\text{-}\thr\) predicates with $m=n^s$, where $m$ and $n$ are the length of output and input, respectively. By partitioning the output bits into groups according to common input bits, high