Advances in Cryptology – ASIACRYPT 2025
Fast Pseudorandom Correlation Functions from Sparse LPN
Lennart Braun
Université Paris Cité, CNRS, IRIF, Paris, France
Geoffroy Couteau
Université Paris Cité, CNRS, IRIF, Paris, France
Kelsey Melissaris
Chalmers University of Technology, Göteborg, Sweden
Mahshid Riahinia
DIENS, École normale supérieure, CNRS, Paris, France
Elahe Sadeghi
University of Texas at Austin, Austin, TX, USA
Keywords:
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.
Publication
Advances in Cryptology – ASIACRYPT 2025. ASIACRYPT 2025. Lecture Notes in Computer Science, vol 16251. Springer, Singapore.
PaperArtifact
Artifact number
asiacrypt/2025/a19
Artifact published
December 31, 2025
Badge
IACR Artifacts Functional
License
This work is licensed under the MIT License.
Note that license information is supplied by the authors and has not been confirmed by the IACR.
BibTeX How to cite
Braun, L., Couteau, G., Melissaris, K., Riahinia, M., Sadeghi, E. (2026). Fast Pseudorandom Correlation Functions from Sparse LPN. In: Hanaoka, G., Yang, BY. (eds) Advances in Cryptology – ASIACRYPT 2025. ASIACRYPT 2025. Lecture Notes in Computer Science, vol 16251. Springer, Singapore. https://doi.org/10.1007/978-981-95-5122-4_14. Artifact available at https://artifacts.iacr.org/asiacrypt/2025/a19