Welcome to the resource topic for 2025/169
Title:
Efficient Pseudorandom Correlation Generators for Any Finite Field
Authors: Zhe Li, Chaoping Xing, Yizhou Yao, Chen Yuan
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 \mathbb{F}_p. For kN OLE correlations, we require O(k\log{N}) communication and O(k^2N\log{N}) computation, where k is an arbitrary integer \geq 2. Previous works either have quadratic computation (Boyle et al. Crypto’19), or can only support fields of size larger than 2 (Bombar et al. Crypto’23).
(ii) We extend the above OLE construction to provide various types of correlations for any finite field. One of the fascinating applications is an efficient PCG for two-party {\em authenticated Boolean multiplication triples}. For kN authenticated triples, we offer PCGs with seed size of O(k^2\log{N}) bits. To our best knowledge, such correlation has not been realized with sublinear communication and quasi-linear computation ever before.
(iii) In addition, the \emph{programmability} admits efficient PCGs for multi-party Boolean triples, and thus the first efficient MPC protocol for Boolean circuits with {\em silent} preprocessing. In particular, we show kN m-party Boolean multiplication triples can be generated in O(m^2k\log{N})-bit communication, while the state-of-the-art FOLEAGE (Asiacrypt’24) requires a broadcast channel and takes mkN+O(m^2\log{kN}) bits communication.
(iv) Finally, we present efficient PCGs for circuit-dependent preprocessing, matrix multiplications triples, and string OTs etc. Compared to previous works, each has its own right.
ePrint: https://eprint.iacr.org/2025/169
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .