Paper 2025/169
Efficient Pseudorandom Correlation Generators for Any Finite Field
Abstract
Correlated randomness lies at the core of efficient modern secure multi-party computation (MPC) protocols. Costs of generating such correlated randomness required for the MPC online phase protocol often constitute a bottleneck in the overall protocol.
A recent paradigm of {\em pseudorandom correlation generator} (PCG) initiated by Boyle et al. (CCS'18, Crypto'19) offers an appealing solution to this issue. In sketch, each party is given a short PCG seed, which can be locally expanded into long correlated strings, satisfying the target correlation. Among various types of correlations, there is oblivious linear evaluation (OLE), a fundamental and useful primitive for typical MPC protocols on arithmetic circuits.
Towards efficient generating a great amount of OLE, and applications to MPC protocols, we establish the following results:
(i) We propose a novel {\em programmable} PCG construction for OLE over any field
Note: Acknowledgement Updated. We've noticed a recent work (https://eprint.iacr.org/2025/892) that claims to break QA-SD assumptions under serveal parameter regimes. Our work is resilient to their attacks by either using Ring-LPN assumptions or using QA-SD assumptions over larger fields as pointed out in Section 5 and Table 1 of that work.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2025
- Keywords
- MPCPseudorandom Correlation Genertors
- Contact author(s)
-
lizh0048 @ e ntu edu sg
xingcp @ sjtu edu cn
yaoyizhou0620 @ sjtu edu cn
chen_yuan @ sjtu edu cn - History
- 2025-05-20: last of 3 revisions
- 2025-02-05: received
- See all versions
- Short URL
- https://ia.cr/2025/169
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2025/169, author = {Zhe Li and Chaoping Xing and Yizhou Yao and Chen Yuan}, title = {Efficient Pseudorandom Correlation Generators for Any Finite Field}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/169}, year = {2025}, url = {https://eprint.iacr.org/2025/169} }