Paper 2026/1281

Resultants Meet Resultant: Improving CICO-1 and CICO-2 Attacks on ZK-Friendly Permutations

Abstract

The increasing usage of Zero-knowledge proof protocols has raised the need for cryptographic primitives that are efficient in that setting, called Arithmetization-oriented primitives. The security of such permutations is commonly evaluated with the CICO-$k$ problem. The best known CICO-$1$ attack against ZK-Friendly permutations over $\mathbb{F}_q^t$ based on $\alpha$-inversions $x\mapsto x^{1/\alpha}$ exploits resultants (ASIACRYPT 2024, CRYPTO 2025). It starts from one input variable $x$ and introduces a temporary variable after each $\alpha$-inversion. With an efficient procedure to eliminate temporary variables, the attack reaches a time and memory complexity of $\tilde{\mathcal{O}}(D_I (2-1/\alpha)^n)$, where $D_I$ is the ideal degree of the CICO-$1$ modeling and $n$ is the number of $\alpha$-inversions. In this work, we study such an approach using two input variables $x_1 , x_2$, and we generalize the temporary variable elimination to that setting. Subsequently, we present a new CICO-$2$ attack framework and a new Start-From-The-Middle (SFTM) CICO-$1$ attack framework. Both our attacks rely on fast bivariate resultants for their final bivariate system solving step. Using resultant algorithms with complexity almost linear in $D_I$, our CICO-$2$ and CICO-$1$ attacks reach a complexity almost linear in $\alpha^n D_I$ and in $D_I$, respectively, which is a first theoretical improvement. Designing an efficient implementation of these resultant algorithms remains a challenge, so for our practical contributions we turn to Villard's algorithm (ISSAC 2018). After adapting it to our context, we obtain practical complexities $\tilde{\mathcal{O}}((\alpha^n D_I)^{\gamma_2})$ and $\tilde{\mathcal{O}}(D_I^{\gamma_1})$ for CICO-$2$ and CICO-$1$ respectively, where $1.2 \le \gamma_1 \le 1.25 \le \gamma_2 \le 1.33$ depending on the chosen linear algebra exponent $2 \le \omega \le 3$. Our attacks improve upon the best known ones against several instances of Anemoi, Rescue and Griffin, successfully breaking $128$-bit and $256$-bit security instances of Rescue in the CICO-$1$ setting and full-round instances of Anemoi and Griffin in the CICO-$2$ setting for the first time. Our implementation of the attack confirms the practicality of the approach.