This course covers the learning outcomes and goals of understanding correlated pseudorandom functions from Variable-Density LPN. Students will learn about correlated pseudorandom functions, low-complexity weak PRFs, secure multi-party computation, MPC with preprocessing Beaver91, PCG, PCF, construction of PCFs, weak PRF, FSS, Dual Learning Parity with (Regular) Noise, exponential stretch, security analysis, and security against XOR-related-key attacks. The teaching method includes theoretical explanations, practical examples, and security analysis. This course is intended for individuals interested in cryptography, secure computation, and theoretical computer science.
Correlated Pseudorandom Functions from Variable-Density LPN
Overview
Syllabus
Intro
Part I: Correlated pseudorandom functions
Part II: Low-complexity weak PRFs
Secure multi-party computation (MPC)
Secure MPC with preprocessing Beaver91
Pseudorandom correlation generator (PCG)
Pseudorandom correlation function (PCF)
Construction of PCFs
Weak pseudorandom function (weak PRF)
Function secret sharing (FSS)
Towards instantiating the building blocks
Dual Learning Parity with (Regular) Noise
Towards exponential stretch
A different point of view
Security Analysis
Security against XOR-related-key attacks
Concrete efficiency
Summary Variable-Density Learning Parity with Noise assumption - can be proven to withstand large class of attacks
Taught by
IEEE FOCS: Foundations of Computer Science
