Skip to main content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Key Recovery Attack on Cubic Simple Matrix Encryption

Published

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 nist-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 nist-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

Keywords

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