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.

Improved Attacks for Characteristic-2 Parameters of the Cubic ABC Simple Matrix Encryption Scheme

Published

Author(s)

Dustin Moody, Ray A. Perlner, 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. One promising approach to cryptanalyzing these schemes has been structural cryptanalysis, based on applying a strategy similar to MinRank attacks to the discrete differential. These attacks however have been signifi cantly more expensive when applied to parameters using fi elds of characteristic 2, which have been the most common choice for published parameters. This disparity is especially great for the cubic version of the Simple Matrix Encryption Scheme. In this work, we demonstrate a technique that can be used to implement a structural attack which is as efficient against parameters of characteristic 2 as are attacks against analogous parameters over higher characteristic fi elds. This attack demonstrates that, not only is the cubic simple matrix scheme susceptible to structural attacks, but that the published parameters claiming 80 bits of security are less secure than claimed (albeit only slightly.) Similar techniques can also be applied to improve structural attacks against the original Simple Matrix Encryption scheme, but they represent only a modest improvement over previous structural attacks. This work therefore demonstrates that choosing a field of characteristic 2 for the Simple Matrix Encryption Scheme or its cubic variant will not provide any additional security value.
Conference Dates
June 26-28, 2017
Conference Location
Utrecht
Conference Title
PQCrypto 2017: The Eighth International Conference on Post-Quantum Cryptography

Keywords

multivariate cryptography, differential invariant, MinRank, encryption

Citation

Moody, D. , Perlner, R. and Smith-Tone, D. (2017), Improved Attacks for Characteristic-2 Parameters of the Cubic ABC Simple Matrix Encryption Scheme, PQCrypto 2017: The Eighth International Conference on Post-Quantum Cryptography, Utrecht, -1, [online], https://doi.org/10.1007/978-3-319-59879-6 (Accessed April 25, 2024)
Created June 28, 2017, Updated June 2, 2021