Pseudorandom Correlation Generators from the Quasi-Abelian Decoding Problem

Secure multi-party computing often enhances efficiency by leveraging correlated randomness. Recently, Boyle et al. showcased the effectiveness of pseudorandom correlation generators (PCGs) in producing substantial correlated (pseudo)randomness, specifically for two-party random oblivious linear evaluations (OLEs). This process involves minimal interactions and subsequent local computations, enabling secure two-party computation with silent pre-processing. The methodology is extendable to N-party through programmable PCGs. However, existing programmable PCGs for OLEs face limitations, as they generate OLEs exclusively over large fields and relying on a recent divisible ring-LPN assumption lacking a robust security foundation. In this talk, I'll introduce the Quasi-Abelian Syndrome Decoding Problem, a broader interpretation of the Quasi-Cyclic decoding problem. The hardness of this new problem enables constructing programmable PCGs for OLE correlation on any field Fq (with q>2). This instantiation is resilient to attacks on the linear test framework and allows a reduction in search to decision, addressing weaknesses in previous constructions. This work is based on a joint work with Maxime Bombar, Geoffroy Couteau and Alain Couvreur.