A new multivariate primitive from CCZ equivalence

Multivariate Cryptography is one of the main candidates for Post-quantum Cryptography. Multivariate schemes are usually constructed by applying two secret affine invertible transformations S, T to a set of multivariate polynomials F (often quadratic). The secret polynomials F posses a trapdoor that allows the legitimate user to find a solution of the corresponding system, while the public polynomials G= S∘ F∘ T look like random polynomials. The polynomials G and F are said to be affine equivalent. In this article, we present a more general way of constructing a multivariate scheme by considering the CCZ equivalence, which has been introduced and studied in the context of vectorial Boolean functions.