Fast Pseudorandom Correlation Functions from Sparse LPN

Pseudorandom Correlation Functions (PCFs) are functions that generate pseudorandom correlated strings. These correlations can then be used to speed up secure computation protocols. In this talk, I present a new and efficient pseudorandom correlation function whose security reduces to the sparse LPN assumption in the random oracle model. Our construction is the first to achieve high concrete efficiency while relying on well-established assumptions: previous candidates either required introducing new assumptions, or had poor concrete performances. We complement our result with an in-depth analysis of the sparse LPN assumption, providing new insight on how to evaluate the strength of concrete sets of parameters. Based on a joint work with Lennart Braun, Geoffroy Couteau, Kelsey Melissaris, and Elahe Sadeghi (ia.cr/2025/1644).