Key Recovery Attack on Cubic Simple Matrix Encryption

Published

August 11, 2016

Author(s)

Ray Perlner, Dustin Moody, Daniel Smith-Tone

Abstract

In the last few years multivariate public key cryptography has experienced an infusion of new ideas for encryption. Among these new strategies is the ABC Simple Matrix family of encryption schemes which utilize the structure of a large matrix algebra to construct effectively invertible systems of nonlinear equations hidden by an isomorphism of polynomials. The cubic version of the ABC Simple Matrix Encryption was developed with provable security in mind and was published including a heuristic security argument claiming that an attack on the scheme should be at least as difficult as solving a random system of quadratic equations over a finite field. In this work, we prove that these claims are erroneous. We present a complete key recovery attack breaking full sized instances of the scheme. Interestingly, the same attack applies to the quadratic version of ABC, but is far less efficient; thus, the enhanced security scheme is less secure than the original.

Proceedings Title

Selected Areas in Cryptography (SAC 2016)

Conference Dates

August 10-12, 2016

Conference Location

St. Johns, Newfoundland, CA

Pub Type

Conferences

Download Paper

Local Download

Keywords

multivariate public key cryptography, differential invariant, MinRank, encryption

Citation

Perlner, R. , Moody, D. and Smith-Tone, D. (2016), Key Recovery Attack on Cubic Simple Matrix Encryption, Selected Areas in Cryptography (SAC 2016), St. Johns, Newfoundland, CA, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=921429 (Accessed November 3, 2025)