A Multivariate Signature Scheme with a Partially Cyclic Public Key

Multivariate public key cryptography is one of the main approaches to guarantee the security of communication in a post-quantum world. Due to its high effciency and modest computational requirements, multivariate cryptography seems especially appropriate for signature schemes for low cost devices. However, multivariate schemes are not yet much used, mainly because of the large size of the public key. In this paper we present a new idea to reduce the public key size of multivariate cryptosystems by proposing a multivariate signature scheme with a partially cyclic public key. The scheme is based on the UOV-Scheme of Kipnis and Patarin, but reduces the size of the public key by about 83 %