TY - GEN
T1 - Efficient pseudorandom correlation generators from ring-lpn
AU - Boyle, Elette
AU - Couteau, Geoffroy
AU - Gilboa, Niv
AU - Ishai, Yuval
AU - Kohl, Lisa
AU - Scholl, Peter
PY - 2020
Y1 - 2020
N2 - Secure multiparty computation can often utilize a trusted source of correlated randomness to achieve better efficiency. A recent line of work, initiated by Boyle et al. (CCS 2018, Crypto 2019), showed how useful forms of correlated randomness can be generated using a cheap, one-time interaction, followed by only “silent” local computation. This is achieved via a pseudorandom correlation generator (PCG), a deterministic function that stretches short correlated seeds into long instances of a target correlation. Previous works constructed concretely efficient PCGs for simple but useful correlations, including random oblivious transfer and vector-OLE, together with efficient protocols to distribute the PCG seed generation. Most of these constructions were based on variants of the Learning Parity with Noise (LPN) assumption. PCGs for other useful correlations had poor asymptotic and concrete efficiency. In this work, we design a new class of efficient PCGs based on different flavors of the ring-LPN assumption. Our new PCGs can generate OLE correlations, authenticated multiplication triples, matrix product correlations, and other types of useful correlations over large fields. These PCGs are more efficient by orders of magnitude than the previous constructions and can be used to improve the preprocessing phase of many existing MPC protocols.
AB - Secure multiparty computation can often utilize a trusted source of correlated randomness to achieve better efficiency. A recent line of work, initiated by Boyle et al. (CCS 2018, Crypto 2019), showed how useful forms of correlated randomness can be generated using a cheap, one-time interaction, followed by only “silent” local computation. This is achieved via a pseudorandom correlation generator (PCG), a deterministic function that stretches short correlated seeds into long instances of a target correlation. Previous works constructed concretely efficient PCGs for simple but useful correlations, including random oblivious transfer and vector-OLE, together with efficient protocols to distribute the PCG seed generation. Most of these constructions were based on variants of the Learning Parity with Noise (LPN) assumption. PCGs for other useful correlations had poor asymptotic and concrete efficiency. In this work, we design a new class of efficient PCGs based on different flavors of the ring-LPN assumption. Our new PCGs can generate OLE correlations, authenticated multiplication triples, matrix product correlations, and other types of useful correlations over large fields. These PCGs are more efficient by orders of magnitude than the previous constructions and can be used to improve the preprocessing phase of many existing MPC protocols.
UR - https://www.scopus.com/pages/publications/85089722128
U2 - 10.1007/978-3-030-56880-1_14
DO - 10.1007/978-3-030-56880-1_14
M3 - Article in proceedings
AN - SCOPUS:85089722128
SN - 9783030568795
T3 - Lecture Notes in Computer Science
SP - 387
EP - 416
BT - Advances in Cryptology - CRYPTO 2020
A2 - Micciancio, Daniele
A2 - Ristenpart, Thomas
PB - Springer
CY - Cham
T2 - 40th Annual International Cryptology Conference, CRYPTO 2020
Y2 - 17 August 2020 through 21 August 2020
ER -