Paper 2022/1014

Correlated Pseudorandomness from Expand-Accumulate Codes

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
Nicolas Resch, Centrum Wiskunde & Informatica
Peter Scholl, Aarhus University

A pseudorandom correlation generator (PCG) is a recent tool for securely generating useful sources of correlated randomness, such as random oblivious transfers (OT) and vector oblivious linear evaluations (VOLE), with low communication cost. We introduce a simple new design for PCGs based on so-called expand-accumulate codes, which first apply a sparse random expander graph to replicate each message entry, and then accumulate the entries by computing the sum of each prefix. Our design offers the following advantages compared to state-of-the-art PCG constructions: - Competitive concrete efficiency backed by provable security against relevant classes of attacks; - An offline-online mode that combines near-optimal cache-friendliness with simple parallelization; - Concretely efficient extensions to pseudorandom correlation functions, which enable incremental generation of new correlation instances on demand, and to new kinds of correlated randomness that include circuit-dependent correlations. To further improve the concrete computational cost, we propose a method for speeding up a full-domain evaluation of a puncturable pseudorandom function (PPRF). This is independently motivated by other cryptographic applications of PPRFs.

Note: There was a mistake in the proof of Theorem 3.10, which this update corrects. The theorem statement is now slightly changed: specifically, we now require C>1/beta^2. We thank Alexander Block, Jonathan Katz and Justin Thaler for bringing this error to our attention and for suggesting the fix.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
multi-party computationpseudorandom correlation generatorslearning 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
nicolas resch @ cwi nl
peter scholl @ cs au dk
2023-03-31: revised
2022-08-05: 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 Nicolas Resch and Peter Scholl},
      title = {Correlated Pseudorandomness from Expand-Accumulate Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1014},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.