Abstract
Multivariate cryptography is one of the challenging candidates for post-quantum cryptography. There exists a huge variety of proposals, most of them have been broken substantially. Multivariate schemes are usually constructed by applying two secret affine invertible transformations to a set of multivariate polynomials (often quadratic). The secret polynomials possess a trapdoor that allows the legitimate user to find a solution of the corresponding system, while the public polynomials look like random polynomials. In [Calderini, M., Caminata, A., Villa, I. A New Multivariate Primitive from CCZ Equivalence. J. Cryptol. 38, 25 (2025)], the authors addressed the above challenge by presenting a promising new way of constructing a multivariate scheme by considering the CCZ equivalence, which has been introduced and studied in the context of vectorial Boolean functions. The resulting proposal is called Pesto with security parameters , where is the number of variables, and the size of the finite base field . In this paper we present an attack against Pesto by constructing an equivalent secret key from the public key. This attack has a precomputation phase with a complexity of [\textrm{max}\left{{\mathcal{O}\left(n^{6}(m-t)\right),\mathcal{O}\left(\frac{(m-t)(n-t)^2(n-t-s)q^s}{\mathcal{P}(q,n-t-s)}\right)}\right}] base field operations on average and an online complexity of [\mathcal{O}(q^s(m-t)(n-t-s) \cdot \min(m-t,n-t-s) + q^st (n-t)^2 + q^st^3)] base field operations to decipher a message or forge a signature, where .
Thus, our attack breaks Pesto for any practical choice of the security parameters and renders the concrete construction underlying Pesto insecure.