Pseudorandom Correlation Functions from Variable-Density LPN, Revisited

Multi Party Computation (MPC) is a very active area of research in cryptography that allows players to compute a function together without sharing their private data. The generation of secret correlated pseudo-random strings is very useful in the various MPC protocols. Pseudo-random correlation functions (PCFs), introduced by Boyle et al in FOCS2020, are a very powerful MPC primitive that allows two parties to generate locally, from short correlated keys, an almost unlimited amount of pseudo-random samples from a target correlation. A candidate for PCF has been introduced by Boyle et al, based on a new Variable Density variant of the Learning Parity with Noise assumption. In the presentation, I will explain the initial construction, and then the various improvements that I have carried out in a work at PKC 2023.