Paper 2025/1644 Original: eprint.iacr.org/2025/1644 ↗
Fast Pseudorandom Correlation Functions from Sparse LPN
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2026-01-12: last updated
- 2025-09-11: published
- Short URL
- https://ia.cr/2025/1644
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2025/1644,
author = {Lennart Braun and Geoffroy Couteau and Kelsey Melissaris and Mahshid Riahinia and Elahe Sadeghi},
title = {Fast Pseudorandom Correlation Functions from Sparse LPN},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1644},
year = {2025},
url = {https://eprint.iacr.org/2025/1644}
}