Pseudorandom Generators

Constructions stretching a short seed into a longer pseudorandom string, and their algebraic structure.

Status	Statement	Tags
	No expanding weak quadratic PRGs Open: whether every family of quadratic Λ(n)-bounded polynomials at stretch m ≥ n^{1+ε} admits an efficient distinguisher from the same evaluations plus bounded independent noise; the paper proves only the i.i.d.-nice special case (Theorem 2) and reports, without proof, that no degree-two candidate survives its attacks experimentally. 3 open	Average Case Hardness Pseudorandom Generatorsimpossibility
	Blockwise-random quadratic recovery Open: whether there is a polynomial-time algorithm that provably recovers the planted input from m = n^{1+eps} published quadratics of the blockwise-random (Lin-Matt) form, sum of a random sparse (perfect-matching) part and an independent random dense part. The paper proves this for i.i.d.-nice polynomial distributions (Theorem 2) but the blockwise-random distribution is not nice, and reports only experimental recovery via a modified semidefinite program. 5 open	Average Case Hardness Pseudorandom Generatorsassumption
	XOR as a Weak 2-Immunizer The single unresolved cell in the source’s own table: XOR fails as a strong 2-immunizer under Alekhnovich, a bilinear pairing fails as a weak one under SXDH, a random oracle succeeds even with auxiliary input. The weak case for XOR is left open with a conjectured answer and a concrete route to it. 4 open	Backdoored Primitives Black Box Separations Pseudorandom Generatorsseparationadaptation (ai)