## CryptoDB

### Paper: Correlated Pseudorandomness from Expand-Accumulate Codes

Authors: Elette Boyle , IDC Herzliya and NTT Research Israel Geoffroy Couteau , CNRS, IRIF, Université de Paris Niv Gilboa , Ben-Gurion University Yuval Ishai , Technion Lisa Kohl , CWI Nicolas Resch , CWI Peter Scholl , Aarhus University Search ePrint Search Google Slides CRYPTO 2022 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.
##### BibTeX
@inproceedings{crypto-2022-32265,
title={Correlated Pseudorandomness from Expand-Accumulate Codes},
publisher={Springer-Verlag},
author={Elette Boyle and Geoffroy Couteau and Niv Gilboa and Yuval Ishai and Lisa Kohl and Nicolas Resch and Peter Scholl},
year=2022
}