Charles Bouillaguet
Sorbonne Université, CNRS, LIP6, France

Claire Delaplace
Laboratoire MIS, Université de Picardie Jules Verne

Mickaël Hamdad
Sorbonne Université, CNRS, LIP6 and Laboratoire MIS, Université de Picardie Jules Verne, France

Damien Vergnaud
Sorbonne Université, CNRS, LIP6, France

Keywords: Quasi-Abelian Syndrome Decoding, Sparse polynomial interpolation, Practical attacks

Abstract

Quasi-Abelian Syndrome Decoding (QA-SD) was introduced by Bombar et al (Crypto 2023) in order to obtain pseudorandom correlation generators for Beaver triples over small fields. This theoretical work was turned into a concrete and efficient protocol called F4OLEage by Bombar et al. (Asiacrypt 2024) that allows several parties to generate Beaver triples over GF(2).

We propose efficient algorithms to solve the decoding problem underlying the QA-SD assumption. We observe that it reduces to a sparse multivariate polynomial interpolation problem over a small finite field where the adversary only has access to random evaluation points, a blind spot in the otherwise rich landscape of sparse multivariate interpolation. We develop new algorithms for this problem: using simple techniques, we interpolate polynomials with up to two monomials. By sending the problem to the field of complex numbers and using convex optimization techniques inspired by the field of ``compressed sensing'', we can interpolate polynomials with more terms.

This enables us to break in practice parameters proposed by Bombar et al. at Crypto'23 and Asiacrypt'24, as well as Li et al. at Eurocrypt'25 (IACR flagship conferences Grand Slam). In the case of the F4OLEage protocol, our implementation recovers all the secrets in a few hours with probability 60\%. This not only invalidates the security proofs, but it also yields real-life privacy attacks against multiparty protocols using the Beaver triples generated by the broken pseudorandom correlation generators.