Pseudorandom Correlation Generators from the Quasi-Abelian Decoding Problem

Secure multiparty computation often benefits from using correlated randomness to achieve better efficiency. Recently, Boyle et al. showed how Pseudorandom Correlation Generators (PCG’s) can be used to generate and distribute a large amount of useful correlated (pseudo)randomness such as random Oblivious Linear Evaluations (OLE’s) to two parties, using minimal interactions, followed solely by local computations. This enables secure two-party computation with silent preprocessing, which can be extended to N-party using so-called programmable PCG’s.

Previous constructions of programmable PCG’s for OLE’s suffer from two downsides: (1) They only generate OLE’s over large fields, and (2) They rely on a rather recent splittable Ring-LPN assumption which lacks from strong security foundations.

In this talk, I will introduce the Quasi-Abelian Syndrome Decoding problem, which generalises the well-known Quasi-Cyclic Decoding Problem, and show how its hardness allows to build programmable PCG’s for the OLE correlation over any field Fq (with q>2). This instantiation resists all attacks from the linear test framework (which encompasses essentially all known generic attacks against variants of the Decoding Problem), and admits a search-to-decision reduction. As a by-product, this work permits to identify weak instantiations which were allowed in previous constructions.

This is based on a joint work with Geoffroy Couteau, Alain Couvreur and Clément Ducros.