Public-Key Cryptography from Learning Parity with Noise - A Code-based Approach to Post-quantum Cryptography

Learning Parity with Noise (LPN) is a notoriously (quantum) hard problem in learning theory and coding theory. It represents the well-known NPC problem "decoding random linear codes" and its average-case 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 how to build postquantum public-key encryption schemes from the hardness of LPN.