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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
multi-party computation pseudorandom correlation generators 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
nicolas resch @ cwi nl
peter scholl @ cs au dk
History
2022-08-07: approved
2022-08-05: received
See all versions
Short URL
https://ia.cr/2022/1014
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1014,
      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{https://eprint.iacr.org/2022/1014}},
      url = {https://eprint.iacr.org/2022/1014}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.