Key Recovery Attack on Cubic Simple Matrix Encryption

Published: August 12, 2016

Author(s)

Ray A. Perlner, Dustin Moody, Daniel C. 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, -1
Pub Type: Conferences

Keywords

multivariate public key cryptography, differential invariant, MinRank, encryption
Created August 12, 2016, Updated April 12, 2017