Paper 2025/1644
Fast Pseudorandom Correlation Functions from Sparse LPN
, Université Paris Cité, French National Centre for Scientific Research, IRIF, Université Paris Cité, French National Centre for Scientific Research, IRIF, Chalmers University of Technology, École Normale Supérieure - PSL, French National Centre for Scientific ResearchAbstract
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.
Note: Corrected asymptotic parameters in Section 3.1 and the computed values of the dual distance in Section 4.3.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in ASIACRYPT 2025
- DOI
- 10.1007/978-981-95-5122-4_14
- Keywords
- PCFSparse LPNVOLEOT
- Contact author(s)
-
lbraun @ irif fr
couteau @ irif fr
kelseym @ chalmers se
mahshid riahinia @ ens fr
elahesadeghi @ utexas edu - History
- 2026-01-12: last of 2 revisions
- 2025-09-11: received
- See all versions
- Short URL
- https://ia.cr/2025/1644
- License
-
CC BY
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},
doi = {10.1007/978-981-95-5122-4_14},
url = {https://eprint.iacr.org/2025/1644}
}
