Structured-Seed Local Pseudorandom Generators and their Applications

Pseudorandom generators are basic tools for simulating randomness efficiently. A local PRG is one where each output bit depends on only a few bits of the seed, which makes them useful in low-depth cryptography and certain complexity-theoretic constructions.

In this talk, I will introduce structured-seed local PRGs (SSL-PRGs), where the seed is not uniform but comes from a simple, efficiently sampleable structured distribution. This small change turns out to broaden what we can build: we can construct SSL-PRGs under assumptions that are much weaker than those needed for standard local PRGs.

The key idea combines PRGs that tolerate “noisy” sparse input with new ways to locally compress sparse vectors. From this, we obtain efficient SSL-PRGs based on variants of the Learning-Parity-with-Noise problem. I will also show how SSL-PRGs recover several known applications such as constant overhead secure computation and hardness-of-learning, under these milder assumptions.