Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding

A recent paradigm put forth by Boyle et al. (CCS 2018, Crypto 2019) showed how pseudorandom correlation generators (PCG) can be used to generate large amounts of useful forms of correlated (pseudo)randomness, using minimal interactions followed solely by local computations, yielding silent secure two-party computation protocols. This can be extended to N -party using programmable PCG’s. Previous works constructed very efficient (non-programmable) PCG’s for correlations such as random oblivious transfers. However, the situation is less satisfying for random oblivious linear evaluations (OLE ’s), their generalisation over large fields. The state-of-the-art work of Boyle et al. (Crypto 2020) constructed programmable PCG’s for OLE, but their work suffers from two important downsides: (1) it only generates OLE ’s over large fields, and (2) it relies on a relatively new “splittable” ring- LPN assumption, which lacks strong security foundations. In this work, we introduce the quasi-abelian syndrome decoding problem (QA- SD ), a family of assumptions which generalises the well-established quasi-cyclic syndrome decoding assumption and allows to construct new programmable PCG’s for OLE over any field F_q with q> 2. Our analysis also sheds light on the security of the ring- LPN assumption used in Boyle et al., Crypto 2020). Using our new PCG’s, we obtain the first efficient N -party silent secure computation protocols for computing general arithmetic circuit over F_q for any q> 2.