Resultants Meet Resultant: Improving CICO-1 and CICO-2 Attacks on ZK-Friendly Permutations (opens in new tab)

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$ an...