Cryptanalysis of a multivariate CCZ scheme

2025/07/21 by Alessio Caminata, Elisa Gorla, Caminata, Alessio +7
Computer Science · #Chaos-based Image/Signal Encryption #Coding theory and cryptography #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Polynomial and algebraic computation #Symbolic Computation (cs.SC)

paper · pdf · doi:10.48550/arxiv.2507.15449

openalex publication_date 2025/07/21 · openalex created_date 2025/09/27 · openalex updated_date 2026/07/28

Abstract

We consider the multivariate scheme Pesto, which was introduced by Calderini, Caminata, and Villa. In this scheme, the public polynomials are obtained by applying a CCZ transformation to a set of quadratic secret polynomials. As a consequence, the public key consists of polynomials of degree 4. In this work, we show that the public degree 4 polynomial system can be efficiently reduced to a system of quadratic polynomials. This seems to suggest that the CCZ transformation may not offer a significant increase in security, contrary to what was initially believed.

Citations

• A new multivariate primitive from CCZ equivalence
• An upper bound for the solving degree in terms of the degree of regularity
• Solving degree, last fall degree, and related invariants
• On the last fall degree of zero-dimensional Weil descent systems
• Codes, Bent Functions and Permutations Suitable For DES-like Cryptosystems

Related

• A new multivariate primitive from CCZ equivalence
• Breaking the Hidden Irreducible Polynomials Scheme
• Multivariate Cryptography with Mappings of Discrete Logarithms and Polynomials
• The complexity of solving a random polynomial system
• A Survey of Multivariate Polynomial Commitment Schemes