Abstract
Secure multiparty computation (MPC) often relies on sources of correlated randomness for better efficiency and simplicity. This is particularly useful for MPC with no honest majority, where input-independent correlated randomness enables a lightweight “non-cryptographic” online phase once the inputs are known. However, since the amount of correlated randomness typically scales with the circuit size of the function being computed, securely generating correlated randomness forms an efficiency bottleneck, involving a large amount of communication and storage.
A natural tool for addressing the above limitations is a pseudorandom correlation generator (PCG). A PCG allows two or more parties to securely generate long sources of useful correlated randomness via a local expansion of correlated short seeds and no interaction. PCGs enable MPC with silent preprocessing, where a small amount of interaction used for securely sampling the seeds is followed by silent local generation of correlated pseudorandomness.
We propose a new class of concretely efficient PCGs for a number of useful correlations based on different flavors of the learning parity with noise assumption. In particular, we present a PCG for oblivious transfer correlations, and show how it can be turned into the first efficient 2-round OT extension protocol of any kind. Further, we provide efficient constructions of PCGs for a broader class of correlations, such as oblivious linear evaluation correlations and authenticated Beaver triples over large fields, based on variants of the ring-LPN assumption.
Based on joint works with Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Peter Rindal, and Peter Scholl.