Abstract:
Multivariate public key cryptosystems form a family of purported quantum-resistant cryptosystems, schemes which remain secure even if an adversary is assumed to have access to a large scale quantum computer. Such cryptosystems publish a public key consisting of a large collection of low degree polynomials in several variables over a finite field. Many cryptographic tasks can be accomplished if the system of equations is unfeasible to invert for an illegitimate user while being efficiently invertible to a legitimate user. We derive several new techniques for determining the security (or insecurity) of multivariate public key cryptosystems. The author presents new security criteria which are practical and are readily proven for a multitude of multivariate schemes. We further demonstrate an attack utilizing a subspace differential invariant illustrating a sharp contrast between cryptosystems which provably have a trivial differential structure and those for which an attack can be realized.