International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Efficient Pseudorandom Correlation Generators from Ring-LPN

Geoffroy Couteau , IRIF, CNRS
Yuval Ishai , Technion
Lisa Kohl , Technion
Elette Boyle , IDC
Peter Scholl , Aarhus University
Niv Gilboa , Ben Gurion University
DOI: 10.1007/978-3-030-56880-1_14 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
Abstract: Secure multiparty computation can often utilize a trusted source of correlated randomness to achieve better efficiency. A recent line of work, initiated by Boyle et al. (CCS 2018, Crypto 2019), showed how useful forms of correlated randomness can be generated using a cheap, one-time interaction, followed by only ``silent'' local computation. This is achieved via a \emph{pseudorandom correlation generator} (PCG), a deterministic function that stretches short correlated seeds into long instances of a target correlation. Previous works constructed concretely efficient PCGs for simple but useful correlations, including random oblivious transfer and vector-OLE, together with efficient protocols to distribute the PCG seed generation. Most of these constructions were based on variants of the Learning Parity with Noise (LPN) assumption. PCGs for other useful correlations had poor asymptotic and concrete efficiency. In this work, we design a new class of efficient PCGs based on different flavors of the {\em ring-LPN} assumption. Our new PCGs can generate OLE correlations, authenticated multiplication triples, matrix product correlations, and other types of useful correlations over large fields. These PCGs are more efficient by orders of magnitude than the previous constructions and can be used to improve the preprocessing phase of many existing MPC protocols.
Video from CRYPTO 2020
  title={Efficient Pseudorandom Correlation Generators from Ring-LPN},
  author={Geoffroy Couteau and Yuval Ishai and Lisa Kohl and Elette Boyle and Peter Scholl and Niv Gilboa},