Correlated Pseudorandomness from Expand-Accumulate Codes
| Autor: | Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, Peter Scholl |
|---|---|
| Přispěvatelé: | Dodis, Yevgeniy, Shrimpton, Thomas |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Zdroj: | Boyle, E, Couteau, G, Gilboa, N, Ishai, Y, Kohl, L, Resch, N & Scholl, P 2022, Correlated Pseudorandomness from Expand-Accumulate Codes . in Y Dodis & T Shrimpton (eds), Advances in Cryptology – CRYPTO 2022-42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings . Springer, Lecture Notes in Computer Science, vol. 13508, pp. 603-633, 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, United States, 15/08/2022 . https://doi.org/10.1007/978-3-031-15979-4_21 Advances in Cryptology – CRYPTO 2022 ISBN: 9783031159787 |
| DOI: | 10.1007/978-3-031-15979-4_21 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|