Paper 2026/1126

A correlation duet: Correlation attacks on correlation generators

Abstract

Pseudo-random correlation generators based on the Quasi-Abelian syndrome decoding problem were first attacked in an article published at Asiacrypt~2025, using compressed sensing. In this paper, we revisit the security of the problem using a more traditional cryptanalytic tool, namely correlation attacks. As a result, we get a new cryptanalysis which outperforms the attack from Asiacrypt 2025 in several directions. It allows recovery of secret error polynomials with larger Hamming weights, runs approximately $1\,000$ times faster and uses $1\,000$ times less memory over $\mathbb{F}_3$. Over $\mathbb{F}_4$, the speed-up and memory gain are even higher. Due to this new attack, it becomes necessary to entirely revisit the parameters of several pseudo-random correlation generator proposals, including FOLEAGE.