Skip to main content
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.

Key Recovery Attack on Cubic Simple Matrix Encryption

Published

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

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 April 18, 2024)
Created August 11, 2016, Updated April 7, 2022