Skip to main content

NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.

Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.

U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Combinatorial Rank Attacks Against the Rectangular Simple Matrix Encryption Scheme

Published

Author(s)

Dustin Moody, Ray A. Perlner, Daniel C. Smith-Tone, Daniel C. Apon, Javier Verbel

Abstract

In 2013, Tao et al. introduced the ABC Simple Matrix Scheme for Encryption, 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 setting 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.
Proceedings Title
Proceedings of PQCrypto 2020: The Eleventh International Conference on Post-Quantum Cryptography
Volume
12100
Conference Dates
April 15-17, 2020
Conference Location
Paris
Conference Title
PQCrypto 2020: The Eleventh International Conference on Post-Quantum Cryptography

Keywords

Multivariate Cryptography, Simple Matrix, encryption, MinRank

Citation

Moody, D. , Perlner, R. , Smith-Tone, D. , Apon, D. and Verbel, J. (2020), Combinatorial Rank Attacks Against the Rectangular Simple Matrix Encryption Scheme, Proceedings of PQCrypto 2020: The Eleventh International Conference on Post-Quantum Cryptography, Paris, -1, [online], https://doi.org/10.1007/978-3-030-44223-1_17 (Accessed October 15, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created April 10, 2020, Updated May 12, 2020
Was this page helpful?