Correlated Pseudorandomness from Expand-Accumulate Codes

Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, Peter Scholl*

*Corresponding author for this work

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

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings
EditorsYevgeniy Dodis, Thomas Shrimpton
Number of pages31
PublisherSpringer
Publication dateOct 2022
Pages603-633
ISBN (Print)9783031159787
DOIs
Publication statusPublished - Oct 2022
Event42nd Annual International Cryptology Conference, CRYPTO 2022 - Santa Barbara, United States
Duration: 15 Aug 202218 Aug 2022

Conference

Conference42nd Annual International Cryptology Conference, CRYPTO 2022
Country/TerritoryUnited States
CitySanta Barbara
Period15/08/202218/08/2022
SeriesLecture Notes in Computer Science
Volume13508
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Correlated Pseudorandomness from Expand-Accumulate Codes'. Together they form a unique fingerprint.

Cite this