Paper 2020/1086

Combinatorial Rank Attacks Against the Rectangular Simple Matrix Encryption Scheme

Daniel Apon, Dustin Moody, Ray Perlner, Daniel Smith-Tone, and Javier Verbel


In 2013, Tao et al. introduced the ABC Simple Matrix Encryption Scheme, a multivariate public key encryption scheme. The scheme boasts great efficiency in encryption and decryption, though it suffers from very large public keys. It was quickly noted that the original proposal, utilizing square matrices, suffered from a very bad decryption failure rate. As a consequence, the designers later published updated parameters, replacing the square matrices with rectangular matrices and altering other parameters to avoid the cryptanalysis of the original scheme presented in 2014 by Moody et al. In this work, we show that making the matrices rectangular, while decreasing the decryption failure rate, actually, and ironically, diminishes security. We show that the combinatorial rank methods employed in the original attack of Moody et al. can be enhanced by the same added degrees of freedom that reduce the decryption failure rate. Moreover, and quite interestingly, if the decryption failure rate is still reasonably high, as exhibited by the proposed parameters, we are able to mount a reaction attack to further enhance the combinatorial rank methods. To our knowledge this is the first instance of a reaction attack creating a significant advantage in this context.

Available format(s)
Publication info
Published elsewhere. PQCrypto 2020
Multivariate CryptographySimple MatrixencryptionMin-Rank
Contact author(s)
daniel apon @ nist gov
dustin moody @ nist gov
ray perlner @ nist gov
daniel smith @ nist gov
javerbel @ unal edu co
2020-09-10: received
Short URL
Creative Commons Attribution


      author = {Daniel Apon and Dustin Moody and Ray Perlner and Daniel Smith-Tone and Javier Verbel},
      title = {Combinatorial Rank Attacks Against the Rectangular Simple Matrix Encryption Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1086},
      year = {2020},
      doi = {10.1007/978-3-030-44223-1_17},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.