Some Recent Progress on Cryptography from Learning Parity with Noise (Yu Yu)

Abstract

Learning Parity with Noise (LPN) is a notoriously hard problem in learning theory and coding theory. It presents the well-known “decoding random linear codes” problem and its average-hardness is also well studied. Recently, there has been renewed interest in building provably secure crypto-systems from LPN.

This talk will introduce the LPN problem and some recent progress on LPN-based cryptographic schemes such as pseudorandom generators in AC0(mod 2), pseudorandom functions in almost constant depth, and public-key encryption schemes.

The talk is a combination of two works (jointly with John Steinberger and Jiang Zhang respectively).

Time

Speaker

Room