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.

NTT Research, Sunnyvale, CA, USA
Lecture Notes in Computer Science

Boyle, E, Couteau, G, Gilboa, N, Ishai, Y, Kohl, L.M, Resch, N.A, & Scholl, P. (2022). Correlated pseudorandomness from expand-accumulate codes. In Advances in Cryptology - CRYPTO 2022 (pp. 603–633). doi:10.1007/978-3-031-15979-4_21