Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN

Explore the concept of Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN in this 25-minute Eurocrypt 2016 conference talk by Yu Yu and John Steinberger. Delve into the intricacies of Learning Parity with Noise (LPN), its hardness, and related work. Examine the main results, including randomized PRGs, PRFs, and their connection to LPN. Gain insights into LPN-based randomized PRG, Bernoulli Noise Extractor, and an alternative Bernoulli noise sampler. Conclude with a discussion on open problems and future directions in this field of cryptography.

Intro
Outline
Learning Parity with Noise (LPN)
Hardness of LPN
Related Work
Main results
(randomized) PRGS, PRFs and LPN
Overview: LPN-based randomized PRG
Bernoulli Noise Extractor (cont'd)
An alternative: Bernoulli noise sampler
Conclusion and open problems