Correlated Pseudorandom Functions from Variable-Density LPN

Explore a 20-minute IEEE conference talk on correlated pseudorandom functions derived from variable-density LPN. Delve into the construction of pseudorandom correlation functions (PCFs) and their applications in secure multi-party computation. Examine weak pseudorandom functions, function secret sharing, and the Variable-Density Learning Parity with Noise assumption. Gain insights into security analysis, including resistance against XOR-related-key attacks, and understand the concrete efficiency of these cryptographic primitives.

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