Simple Matrix – A Multivariate Public Key Cryptosystem (MPKC) for Encryption

•Proposal of a new multivariate encryption scheme.•Improvement of the SimpleMatrix scheme of PQCrypto 2013.•Faster decryption.•Probability of decryption failures is reduced.

Multivariate cryptography is one of the main candidates to guarantee the security of communication in the presence of quantum computers. While there exist a large number of secure and efficient multivariate signature schemes, the number of practical multivariate encryption schemes is somewhat limited. In this paper we present our results on creating a new multivariate encryption scheme, which is an extension of the original SimpleMatrix encryption scheme of PQCrypto 2013. Our scheme allows fast en- and decryption and resists all known attacks against multivariate cryptosystems. Furthermore, we present a new idea to solve the decryption failure problem of the original SimpleMatrix encryption scheme.