Efficient pseudorandom correlation generators from ring-lpn

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Elette Boyle, Interdisciplinary Center Herzliya
  • ,
  • Geoffroy Couteau, Inria Paris and IRIF
  • ,
  • Niv Gilboa, Ben-Gurion University of the Negev
  • ,
  • Yuval Ishai, Technion-Israel Institute of Technology
  • ,
  • Lisa Kohl, Technion-Israel Institute of Technology
  • ,
  • Peter Scholl

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2020
EditorsDaniele Micciancio, Thomas Ristenpart
Number of pages30
Place of publicationCham
Publication year2020
ISBN (print)9783030568795
ISBN (Electronic)978-3-030-56880-1
Publication statusPublished - 2020
Event40th Annual International Cryptology Conference, CRYPTO 2020 - Santa Barbara, United States
Duration: 17 Aug 202021 Aug 2020


Conference40th Annual International Cryptology Conference, CRYPTO 2020
LandUnited States
BySanta Barbara
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 195878100