Paper 2022/1035

Efficient Pseudorandom Correlation Generators from Ring-LPN

Elette Boyle, IDC Herzliya, NTT Research
Geoffroy Couteau, IRIF
Niv Gilboa, Ben-Gurion University of the Negev
Yuval Ishai, Technion – Israel Institute of Technology
Lisa Kohl, Centrum Wiskunde & Informatica
Peter Scholl, Aarhus University

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 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 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.

Note: Full version. See Section 1.2 for changes since the original publication.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2020
pseudorandom correlation generators multi-party computation learning parity with noise
Contact author(s)
eboyle @ alum mit edu
couteau @ irif fr
niv gilboa @ gmail com
yuvali @ cs technion ac il
lisa kohl @ cwi nl
peter scholl @ cs au dk
2022-08-11: approved
2022-08-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Geoffroy Couteau and Niv Gilboa and Yuval Ishai and Lisa Kohl and Peter Scholl},
      title = {Efficient Pseudorandom Correlation Generators from Ring-LPN},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1035},
      year = {2022},
      doi = {10.1007/978-3-030-56880-1_14},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.