International Association
for Cryptologic Research

Quasi-Abelian Syndrome Decoding (QA-SD) was introduced by Bombar et al (Crypto 2023) in order to obtain pseudorandom correla- tion 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 under- lying 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 inter- polate 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.