International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Fast Pseudorandom Correlation Functions from Sparse LPN

Authors:
Lennart Braun , Université Paris Cité, CNRS, IRIF, F-75013, Paris, France
Geoffroy Couteau , Université Paris Cité, CNRS, IRIF, F-75013, Paris, France
Kelsey Melissaris , Chalmers University of Technology, Göteborg, Sweden
Mahshid Riahinia , DIENS, Ecole Normale Supérieure, CNRS, Inria, PSL University, Paris, France
Elahe Sadeghi , University of Texas at Austin
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2025
Abstract: We introduce 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.
BibTeX
@inproceedings{asiacrypt-2025-36143,
  title={Fast Pseudorandom Correlation Functions from Sparse LPN},
  publisher={Springer-Verlag},
  author={Lennart Braun and Geoffroy Couteau and Kelsey Melissaris and Mahshid Riahinia and Elahe Sadeghi},
  year=2025
}