Welcome to the resource topic for 2022/1014
Title:
Correlated Pseudorandomness from Expand-Accumulate Codes
Authors: Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, Peter Scholl
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.
ePrint: https://eprint.iacr.org/2022/1014
Talk: https://www.youtube.com/watch?v=6Xc5TIU5rdw
Slides: https://iacr.org/submit/files/slides/2022/crypto/crypto2022/429/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .