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.